Hi,
This is mostly a re-write of Paul Turner and Andrew Hunter's restartable
critical sections (percpu atomics), which brings the following main
benefits over Paul Turner's prior version (v2):
- The ABI is now architecture-agnostic, and it requires fewer
instruction on the user-space fast path,
- Ported to ARM 32, in addition to cover x86 32/64. Adding support
for new architectures is now trivial,
- Progress is ensured by a fall-back to locking (purely userspace)
when single-stepped by a debugger.
This is v7, as it derives from my prior getcpu cache and thread local
ABI patchsets. You will find benchmark results in the changelog of
patch 1/7.
Feedback is welcome!
Thanks,
Mathieu
Mathieu Desnoyers (7):
Restartable sequences system call
tracing: instrument restartable sequences
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
Restartable sequences: self-tests
MAINTAINERS | 7 +
arch/Kconfig | 7 +
arch/arm/Kconfig | 1 +
arch/arm/include/uapi/asm/unistd.h | 1 +
arch/arm/kernel/calls.S | 1 +
arch/arm/kernel/signal.c | 7 +
arch/x86/Kconfig | 1 +
arch/x86/entry/common.c | 1 +
arch/x86/entry/syscalls/syscall_32.tbl | 1 +
arch/x86/entry/syscalls/syscall_64.tbl | 1 +
arch/x86/kernel/signal.c | 6 +
fs/exec.c | 1 +
include/linux/sched.h | 68 ++
include/trace/events/rseq.h | 60 ++
include/uapi/linux/Kbuild | 1 +
include/uapi/linux/rseq.h | 85 +++
init/Kconfig | 13 +
kernel/Makefile | 1 +
kernel/fork.c | 2 +
kernel/rseq.c | 243 +++++++
kernel/sched/core.c | 1 +
kernel/sys_ni.c | 3 +
tools/testing/selftests/rseq/.gitignore | 3 +
tools/testing/selftests/rseq/Makefile | 13 +
.../testing/selftests/rseq/basic_percpu_ops_test.c | 279 ++++++++
tools/testing/selftests/rseq/basic_test.c | 106 +++
tools/testing/selftests/rseq/param_test.c | 707 +++++++++++++++++++++
tools/testing/selftests/rseq/rseq.c | 200 ++++++
tools/testing/selftests/rseq/rseq.h | 449 +++++++++++++
29 files changed, 2269 insertions(+)
create mode 100644 include/trace/events/rseq.h
create mode 100644 include/uapi/linux/rseq.h
create mode 100644 kernel/rseq.c
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.c
create mode 100644 tools/testing/selftests/rseq/rseq.h
--
2.1.4
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)
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 locking-based
fall-back, purely implemented in user-space, is proposed here to deal
with debugger single-stepping. This fallback interacts with rseq_start()
and rseq_finish(), which force retries in response to concurrent
lock-based activity.
Here are benchmarks of counter increment in various scenarios compared
to restartable sequences:
ARMv7 Processor rev 4 (v7l)
Machine model: Cubietruck
Counter increment speed (ns/increment)
1 thread 2 threads
global increment (baseline) 6 N/A
percpu rseq increment 50 52
percpu rseq spinlock 94 94
global atomic increment 48 74 (__sync_add_and_fetch_4)
global atomic CAS 50 172 (__sync_val_compare_and_swap_4)
global pthread mutex 148 862
ARMv7 Processor rev 10 (v7l)
Machine model: Wandboard
Counter increment speed (ns/increment)
1 thread 4 threads
global increment (baseline) 7 N/A
percpu rseq increment 50 50
percpu rseq spinlock 82 84
global atomic increment 44 262 (__sync_add_and_fetch_4)
global atomic CAS 46 316 (__sync_val_compare_and_swap_4)
global pthread mutex 146 1400
x86-64 Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz:
Counter increment speed (ns/increment)
1 thread 8 threads
global increment (baseline) 3.0 N/A
percpu rseq increment 3.6 3.8
percpu rseq spinlock 5.6 6.2
global LOCK; inc 8.0 166.4
global LOCK; cmpxchg 13.4 435.2
global pthread mutex 25.2 1363.6
* 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 migration 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
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
2855 bytes, and the data size increase of vmlinux is 1024 bytes.
* CONFIG_RSEQ=n
text data bss dec hex filename
9964559 4256280 962560 15183399 e7ae27 vmlinux.norseq
* CONFIG_RSEQ=y
text data bss dec hex filename
9967414 4257304 962560 15187278 e7bd4e vmlinux.rseq
[1] https://lwn.net/Articles/650333/
[2] http://www.linuxplumbersconf.org/2013/ocw/system/presentations/1695/original/LPC%20-%20PerCpu%20Atomics.pdf
Link: http://lkml.kernel.org/r/20151027235635.16059.11630.stgit@pjt-glaptop.roam.corp.google.com
Link: http://lkml.kernel.org/r/20150624222609.6116.86035.stgit@kitami.mtv.corp.google.com
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers-vg+e7yoeK/dWk0Htik3J/w@public.gmane.org>
CC: Thomas Gleixner <redacted>
CC: Paul Turner <redacted>
CC: Andrew Hunter <redacted>
CC: Peter Zijlstra <redacted>
CC: Andy Lutomirski <redacted>
CC: Andi Kleen <andi-Vw/NltI1exuRpAAqCnN02g@public.gmane.org>
CC: Dave Watson <redacted>
CC: Chris Lameter <redacted>
CC: Ingo Molnar <redacted>
CC: "H. Peter Anvin" <redacted>
CC: Ben Maurer <redacted>
CC: Steven Rostedt <redacted>
CC: "Paul E. McKenney" <redacted>
CC: Josh Triplett <redacted>
CC: Linus Torvalds <torvalds-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org>
CC: Andrew Morton <akpm-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org>
CC: Russell King <linux-lFZ/pmaqli7XmaaqVzeoHQ@public.gmane.org>
CC: Catalin Marinas <redacted>
CC: Will Deacon <redacted>
CC: Michael Kerrisk <redacted>
CC: Boqun Feng <redacted>
CC: linux-api-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
---
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.
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, int flags);
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.
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 can be used to check whether rseq is registered for the
current thread.
The layout of struct rseq is as follows:
Structure alignment
This structure needs to be aligned on multiples of 64
bytes.
Structure size
This structure has a fixed size of 128 bytes.
Fields
cpu_id
Cache of the CPU number on which the calling thread is
running.
event_counter
Restartable sequences event_counter field.
rseq_cs
Restartable sequences rseq_cs field. Points to a struct
rseq_cs.
The layout of struct rseq_cs is as follows:
Structure alignment
This structure needs to be aligned on multiples of 64
bytes.
Structure size
This structure has a fixed size of 192 bytes.
Fields
start_ip
Instruction pointer address of the first instruction of
the sequence of consecutive assembly instructions.
post_commit_ip
Instruction pointer 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 flags argument is currently unused and must be specified as
0.
Typically, a library or application will keep the rseq struc‐
ture in a thread-local storage variable, or other memory areas
belonging to each thread. It is recommended to perform volatile
reads of the thread-local cache to prevent the compiler from
doing load tearing. An alternative approach is to read each
field from inline assembly.
Each thread is responsible for registering its rseq structure.
Only one rseq structure address can be registered per thread.
Once set, the rseq address is idempotent for a given thread.
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 single-copy atomicity semantics, which guarantee
that other threads performing single-copy atomic reads of the
cpu number cache will always observe a consistent value.
Memory registered as rseq structure should never be deallocated
before the thread which registered it exits: specifically, it
should not be freed, and the library containing the registered
thread-local storage should not be dlclose'd. Violating this
constraint may cause a SIGSEGV signal to be delivered to the
thread.
Unregistration of associated rseq structure is implicitly per‐
formed when a thread or process exit.
RETURN VALUE
A return value of 0 indicates success. On error, -1 is
returned, and errno is set appropriately.
ERRORS
EINVAL Either flags is non-zero, or rseq contains an address
which is not appropriately aligned.
ENOSYS The rseq() system call is not implemented by this ker‐
nel.
EFAULT rseq is an invalid address.
EBUSY The rseq argument contains a non-NULL address which dif‐
fers from the memory location already registered for
this thread.
ENOENT The rseq argument is NULL, but no memory location is
currently registered for this thread.
VERSIONS
The rseq() system call was added in Linux 4.X (TODO).
CONFORMING TO
rseq() is Linux-specific.
EXAMPLE
The following code uses the rseq() system call to keep a
thread-local storage variable up to date with the current CPU
number, with a fallback on sched_getcpu(3) if the cache is not
available. For example simplicity, it is done in main(), but
multithreaded programs would need to invoke rseq() from each
program thread.
#define _GNU_SOURCE
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <stdint.h>
#include <sched.h>
#include <stddef.h>
#include <errno.h>
#include <string.h>
#include <sys/syscall.h>
#include <linux/rseq.h>
static __thread volatile struct rseq rseq_state = {
.u.e.cpu_id = -1,
};
static int
sys_rseq(volatile struct rseq *rseq_abi, int flags)
{
return syscall(__NR_rseq, rseq_abi, flags);
}
static int32_t
rseq_current_cpu_raw(void)
{
return rseq_state.u.e.cpu_id;
}
static int32_t
rseq_current_cpu(void)
{
int32_t cpu;
cpu = rseq_current_cpu_raw();
if (cpu < 0)
cpu = sched_getcpu();
return cpu;
}
static int
rseq_init_current_thread(void)
{
int rc;
rc = sys_rseq(&rseq_state, 0);
if (rc) {
fprintf(stderr, "Error: sys_rseq(...) failed(%d): %s\n",
errno, strerror(errno));
return -1;
}
return 0;
}
int
main(int argc, char **argv)
{
if (rseq_init_current_thread()) {
fprintf(stderr,
"Unable to initialize restartable sequences.\n");
fprintf(stderr, "Using sched_getcpu() as fallback.\n");
}
printf("Current CPU number: %d\n", rseq_current_cpu());
exit(EXIT_SUCCESS);
}
SEE ALSO
sched_getcpu(3)
Linux 2016-07-19 RSEQ(2)
---
MAINTAINERS | 7 ++
arch/Kconfig | 7 ++
fs/exec.c | 1 +
include/linux/sched.h | 68 ++++++++++++++
include/uapi/linux/Kbuild | 1 +
include/uapi/linux/rseq.h | 85 +++++++++++++++++
init/Kconfig | 13 +++
kernel/Makefile | 1 +
kernel/fork.c | 2 +
kernel/rseq.c | 231 ++++++++++++++++++++++++++++++++++++++++++++++
kernel/sched/core.c | 1 +
kernel/sys_ni.c | 3 +
12 files changed, 420 insertions(+)
create mode 100644 include/uapi/linux/rseq.h
create mode 100644 kernel/rseq.c
@@ -1918,6 +1919,10 @@ struct task_struct {#ifdef CONFIG_MMUstructtask_struct*oom_reaper_list;#endif+#ifdef CONFIG_RSEQ+structrseq__user*rseq;+uint32_trseq_event_counter;+#endif/* CPU-specific state of this task */structthread_structthread;/*
@@ -0,0 +1,231 @@+/*+*Restartablesequencessystemcall+*+*Restartablesequencesarealightweightinterfacethatallows+*user-levelcodetobeexecutedatomicallyrelativetoscheduler+*preemptionandsignaldelivery.Typicallyusedforimplementing+*per-cpuoperations.+*+*Thisprogramisfreesoftware;youcanredistributeitand/ormodify+*itunderthetermsoftheGNUGeneralPublicLicenseaspublishedby+*theFreeSoftwareFoundation;eitherversion2oftheLicense,or+*(atyouroption)anylaterversion.+*+*Thisprogramisdistributedinthehopethatitwillbeuseful,+*butWITHOUTANYWARRANTY;withouteventheimpliedwarrantyof+*MERCHANTABILITYorFITNESSFORAPARTICULARPURPOSE.Seethe+*GNUGeneralPublicLicenseformoredetails.+*+*Copyright(C)2015,Google,Inc.,+*PaulTurner<pjt-hpIqsD4AKlfQT0dZR+AlfA@public.gmane.org>andAndrewHunter<ahh-hpIqsD4AKlfQT0dZR+AlfA@public.gmane.org>+*Copyright(C)2015-2016,EfficiOSInc.,+*MathieuDesnoyers<mathieu.desnoyers-vg+e7yoeK/dWk0Htik3J/w@public.gmane.org>+*/++#include<linux/sched.h>+#include<linux/uaccess.h>+#include<linux/syscalls.h>+#include<linux/compat.h>+#include<linux/rseq.h>+#include<asm/ptrace.h>++/*+*Eachrestartablesequenceassemblyblockdefinesa"struct rseq_cs"+*structurewhichdescribesthepost_commit_ipaddress,andthe+*abort_ipaddresswherethekernelshouldmovethethreadinstruction+*pointerifarseqcriticalsectionassemblyblockispreemptedorif+*asignalisdeliveredontopofarseqcriticalsectionassembly+*block.Italsocontainsastart_ip,whichistheaddressofthestart+*oftherseqassemblyblock,whichisusefultodebuggers.+*+*Thealgorithmforarestartablesequenceassemblyblockisas+*follows:+*+*rseq_start()+*+*0.Userspaceloadsthecurrenteventcountervaluefromthe+*event_counterfieldoftheregisteredstructrseqTLSarea,+*+*rseq_finish()+*+*Steps[1]-[3](inclusive)needtobeasequenceofinstructionsin+*userspacethatcanhandlebeingmovedtotheabort_ipbetweenany+*ofthoseinstructions.+*+*Theabort_ipaddressneedstobeequalorabovethepost_commit_ip.+*Step[4]andthefailurecodestep[F1]needtobeataddresses+*equalorabovethepost_commit_ip.+*+*1.Userspacestorestheaddressofthestructrseqcsrseq+*assemblyblockdescriptorintotherseq_csfieldofthe+*registeredstructrseqTLSarea.+*+*2.Userspaceteststoseewhetherthecurrenteventcountervalues+*matchthoseloadedat[0].Manuallyjumpingto[F1]incaseof+*amismatch.+*+*Notethatifwearepreemptedorinterruptedbyasignal+*after[1]andbeforepost_commit_ip,thenthekernelalso+*performsthecomparisonperformedin[2],andconditionally+*clearsrseq_cs,thenjumpsustoabort_ip.+*+*3.Userspacecriticalsectionfinalinstructionbefore+*post_commit_ipisthecommit.Thecriticalsectionis+*self-terminating.+*[post_commit_ip]+*+*4.Userspaceclearstherseq_csfieldofthestructrseq+*TLSarea.+*+*5.Returntrue.+*+*Onfailureat[2]:+*+*F1.Userspaceclearstherseq_csfieldofthestructrseq+*TLSarea.Followedbystep[F2].+*+*[abort_ip]+*F2.Returnfalse.+*/++staticintrseq_increment_event_counter(structtask_struct*t)+{+if(__put_user(++t->rseq_event_counter,+&t->rseq->u.e.event_counter))+return-1;+return0;+}++staticintrseq_get_rseq_cs(structtask_struct*t,+void__user**post_commit_ip,+void__user**abort_ip)+{+unsignedlongptr;+structrseq_cs__user*rseq_cs;++if(__get_user(ptr,&t->rseq->rseq_cs))+return-1;+if(!ptr)+return0;+#ifdef CONFIG_COMPAT+if(in_compat_syscall()){+rseq_cs=compat_ptr((compat_uptr_t)ptr);+if(get_user(ptr,&rseq_cs->post_commit_ip))+return-1;+*post_commit_ip=compat_ptr((compat_uptr_t)ptr);+if(get_user(ptr,&rseq_cs->abort_ip))+return-1;+*abort_ip=compat_ptr((compat_uptr_t)ptr);+return0;+}+#endif+rseq_cs=(structrseq_cs__user*)ptr;+if(get_user(ptr,&rseq_cs->post_commit_ip))+return-1;+*post_commit_ip=(void__user*)ptr;+if(get_user(ptr,&rseq_cs->abort_ip))+return-1;+*abort_ip=(void__user*)ptr;+return0;+}++staticintrseq_ip_fixup(structpt_regs*regs)+{+structtask_struct*t=current;+void__user*post_commit_ip=NULL;+void__user*abort_ip=NULL;++if(rseq_get_rseq_cs(t,&post_commit_ip,&abort_ip))+return-1;++/* Handle potentially being within a critical section. */+if((void__user*)instruction_pointer(regs)<post_commit_ip){+/*+*Weneedtoclearrseq_csuponentryintoasignal+*handlernestedontopofarseqassemblyblock,so+*thesignalhandlerwillnotbefixedupifitself+*interruptedbyanestedsignalhandlerorpreempted.+*/+if(clear_user(&t->rseq->rseq_cs,+sizeof(t->rseq->rseq_cs)))+return-1;++/*+*Wesetthisafterpotentiallyfailingin+*clear_usersothatthesignalarrivesatthe+*faultingrip.+*/+instruction_pointer_set(regs,(unsignedlong)abort_ip);+}+return0;+}++/*+*Thisresumehandlershouldalwaysbeexecutedbetweenanyof:+*-preemption,+*-signaldelivery,+*andreturntouser-space.+*/+void__rseq_handle_notify_resume(structpt_regs*regs)+{+structtask_struct*t=current;++if(unlikely(t->flags&PF_EXITING))+return;+if(!access_ok(VERIFY_WRITE,t->rseq,sizeof(*t->rseq)))+gotoerror;+if(__put_user(raw_smp_processor_id(),&t->rseq->u.e.cpu_id))+gotoerror;+if(rseq_increment_event_counter(t))+gotoerror;+if(rseq_ip_fixup(regs))+gotoerror;+return;++error:+force_sig(SIGSEGV,t);+}++/*+*sys_rseq-setuprestartablesequencesforcallerthread.+*/+SYSCALL_DEFINE2(rseq,structrseq__user*,rseq,int,flags)+{+if(unlikely(flags))+return-EINVAL;+if(!rseq){+if(!current->rseq)+return-ENOENT;+return0;+}++if(current->rseq){+/*+*Ifrseqisalreadyregistered,checkwhether+*theprovidedaddressdiffersfromtheprior+*one.+*/+if(current->rseq!=rseq)+return-EBUSY;+}else{+/*+*Iftherewasnorseqpreviouslyregistered,+*weneedtoensuretheprovidedrseqis+*properlyalignedandvalid.+*/+if(!IS_ALIGNED((unsignedlong)rseq,sizeof(uint64_t)))+return-EINVAL;+if(!access_ok(VERIFY_WRITE,rseq,sizeof(*rseq)))+return-EFAULT;+current->rseq=rseq;+/*+*Ifrseqwaspreviouslyinactive,andhasjust+*beenregistered,ensurethecpu_idand+*event_counterfieldsareupdatedbefore+*returningtouser-space.+*/+rseq_set_notify_resume(current);+}++return0;+}
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.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
CC: Russell King <redacted>
CC: Catalin Marinas <catalin.marinas@arm.com>
CC: Will Deacon <redacted>
CC: Thomas Gleixner <redacted>
CC: Paul Turner <redacted>
CC: Andrew Hunter <redacted>
CC: Peter Zijlstra <peterz@infradead.org>
CC: Andy Lutomirski <luto@amacapital.net>
CC: Andi Kleen <redacted>
CC: Dave Watson <redacted>
CC: Chris Lameter <redacted>
CC: Ingo Molnar <mingo@redhat.com>
CC: Ben Maurer <redacted>
CC: Steven Rostedt <rostedt@goodmis.org>
CC: "Paul E. McKenney" <redacted>
CC: Josh Triplett <josh@joshtriplett.org>
CC: Linus Torvalds <torvalds@linux-foundation.org>
CC: Andrew Morton <akpm@linux-foundation.org>
CC: Boqun Feng <redacted>
CC: linux-api@vger.kernel.org
---
arch/arm/Kconfig | 1 +
arch/arm/kernel/signal.c | 7 +++++++
2 files changed, 8 insertions(+)
@@ -134,8 +141,13 @@ static int rseq_ip_fixup(struct pt_regs *regs)structtask_struct*t=current;void__user*post_commit_ip=NULL;void__user*abort_ip=NULL;+intret;-if(rseq_get_rseq_cs(t,&post_commit_ip,&abort_ip))+ret=rseq_get_rseq_cs(t,&post_commit_ip,&abort_ip);+trace_rseq_ip_fixup((void__user*)instruction_pointer(regs),+post_commit_ip,abort_ip,t->rseq_event_counter,+ret);+if(ret)return-1;/* Handle potentially being within a critical section. */
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.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers-vg+e7yoeK/dWk0Htik3J/w@public.gmane.org>
CC: Russell King <linux-lFZ/pmaqli7XmaaqVzeoHQ@public.gmane.org>
CC: Catalin Marinas <redacted>
CC: Will Deacon <redacted>
CC: Thomas Gleixner <redacted>
CC: Paul Turner <redacted>
CC: Andrew Hunter <redacted>
CC: Peter Zijlstra <redacted>
CC: Andy Lutomirski <redacted>
CC: Andi Kleen <andi-Vw/NltI1exuRpAAqCnN02g@public.gmane.org>
CC: Dave Watson <redacted>
CC: Chris Lameter <redacted>
CC: Ingo Molnar <redacted>
CC: Ben Maurer <redacted>
CC: Steven Rostedt <redacted>
CC: "Paul E. McKenney" <redacted>
CC: Josh Triplett <redacted>
CC: Linus Torvalds <torvalds-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org>
CC: Andrew Morton <akpm-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org>
CC: Boqun Feng <redacted>
CC: linux-api-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
---
arch/arm/include/uapi/asm/unistd.h | 1 +
arch/arm/kernel/calls.S | 1 +
2 files changed, 2 insertions(+)
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.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers-vg+e7yoeK/dWk0Htik3J/w@public.gmane.org>
CC: Russell King <linux-lFZ/pmaqli7XmaaqVzeoHQ@public.gmane.org>
CC: Catalin Marinas <redacted>
CC: Will Deacon <redacted>
CC: Thomas Gleixner <redacted>
CC: Paul Turner <redacted>
CC: Andrew Hunter <redacted>
CC: Peter Zijlstra <redacted>
CC: Andy Lutomirski <redacted>
CC: Andi Kleen <andi-Vw/NltI1exuRpAAqCnN02g@public.gmane.org>
CC: Dave Watson <redacted>
CC: Chris Lameter <redacted>
CC: Ingo Molnar <redacted>
CC: "H. Peter Anvin" <redacted>
CC: Ben Maurer <redacted>
CC: Steven Rostedt <redacted>
CC: "Paul E. McKenney" <redacted>
CC: Josh Triplett <redacted>
CC: Linus Torvalds <torvalds-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org>
CC: Andrew Morton <akpm-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org>
CC: Boqun Feng <redacted>
CC: linux-api-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
---
arch/x86/Kconfig | 1 +
arch/x86/entry/common.c | 1 +
arch/x86/kernel/signal.c | 6 ++++++
3 files changed, 8 insertions(+)
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.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
CC: Russell King <redacted>
CC: Catalin Marinas <catalin.marinas@arm.com>
CC: Will Deacon <redacted>
CC: Thomas Gleixner <redacted>
CC: Paul Turner <redacted>
CC: Andrew Hunter <redacted>
CC: Peter Zijlstra <peterz@infradead.org>
CC: Andy Lutomirski <luto@amacapital.net>
CC: Andi Kleen <redacted>
CC: Dave Watson <redacted>
CC: Chris Lameter <redacted>
CC: Ingo Molnar <mingo@redhat.com>
CC: "H. Peter Anvin" <hpa@zytor.com>
CC: Ben Maurer <redacted>
CC: Steven Rostedt <rostedt@goodmis.org>
CC: "Paul E. McKenney" <redacted>
CC: Josh Triplett <josh@joshtriplett.org>
CC: Linus Torvalds <torvalds@linux-foundation.org>
CC: Andrew Morton <akpm@linux-foundation.org>
CC: Boqun Feng <redacted>
CC: linux-api@vger.kernel.org
---
arch/x86/entry/syscalls/syscall_32.tbl | 1 +
arch/x86/entry/syscalls/syscall_64.tbl | 1 +
2 files changed, 2 insertions(+)
Implements two basic tests of RSEQ functionality, and one more
exhaustive parameterizable test.
The first, "basic_test" only asserts that RSEQ works moderately
correctly.
E.g. that:
- The CPUID pointer works
- Code infinitely looping within a critical section will eventually be
interrupted.
- Critical sections are interrupted by signals.
"basic_percpu_ops_test" is a slightly more "realistic" variant,
implementing a few simple per-cpu operations and testing their
correctness.
"param_test" is a parametrizable restartable sequences test. See
the "--help" output for usage.
As part of those tests, a helper library "rseq" implements a user-space
API around restartable sequences. It takes care of ensuring progress in
case of debugger single-stepping with a fall-back to locking, and
exposes the instruction pointer addresses where the rseq assembly blocks
begin and end, as well as the associated abort instruction pointer, in
the __rseq_table section. This section allows debuggers may know where
to place breakpoints when single-stepping through assembly blocks which
may be aborted at any point by the kernel.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
CC: Russell King <redacted>
CC: Catalin Marinas <catalin.marinas@arm.com>
CC: Will Deacon <redacted>
CC: Thomas Gleixner <redacted>
CC: Paul Turner <redacted>
CC: Andrew Hunter <redacted>
CC: Peter Zijlstra <peterz@infradead.org>
CC: Andy Lutomirski <luto@amacapital.net>
CC: Andi Kleen <redacted>
CC: Dave Watson <redacted>
CC: Chris Lameter <redacted>
CC: Ingo Molnar <mingo@redhat.com>
CC: "H. Peter Anvin" <hpa@zytor.com>
CC: Ben Maurer <redacted>
CC: Steven Rostedt <rostedt@goodmis.org>
CC: "Paul E. McKenney" <redacted>
CC: Josh Triplett <josh@joshtriplett.org>
CC: Linus Torvalds <torvalds@linux-foundation.org>
CC: Andrew Morton <akpm@linux-foundation.org>
CC: Boqun Feng <redacted>
CC: linux-api@vger.kernel.org
---
tools/testing/selftests/rseq/.gitignore | 3 +
tools/testing/selftests/rseq/Makefile | 13 +
.../testing/selftests/rseq/basic_percpu_ops_test.c | 279 ++++++++
tools/testing/selftests/rseq/basic_test.c | 106 +++
tools/testing/selftests/rseq/param_test.c | 707 +++++++++++++++++++++
tools/testing/selftests/rseq/rseq.c | 200 ++++++
tools/testing/selftests/rseq/rseq.h | 449 +++++++++++++
7 files changed, 1757 insertions(+)
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.c
create mode 100644 tools/testing/selftests/rseq/rseq.h
@@ -0,0 +1,279 @@+#define _GNU_SOURCE+#include<assert.h>+#include<pthread.h>+#include<sched.h>+#include<stdint.h>+#include<stdio.h>+#include<stdlib.h>+#include<string.h>++#include"rseq.h"++staticstructrseq_lockrseq_lock;++structpercpu_lock_entry{+intptr_tv;+}__attribute__((aligned(128)));++structpercpu_lock{+structpercpu_lock_entryc[CPU_SETSIZE];+};++structtest_data_entry{+intcount;+}__attribute__((aligned(128)));++structspinlock_test_data{+structpercpu_locklock;+structtest_data_entryc[CPU_SETSIZE];+intreps;+};++structpercpu_list_node{+intptr_tdata;+structpercpu_list_node*next;+};++structpercpu_list_entry{+structpercpu_list_node*head;+}__attribute__((aligned(128)));++structpercpu_list{+structpercpu_list_entryc[CPU_SETSIZE];+};++/* A simple percpu spinlock. Returns the cpu lock was acquired on. */+intrseq_percpu_lock(structpercpu_lock*lock)+{+structrseq_staterseq_state;+intptr_t*targetptr,newval;+intcpu;+boolresult;++for(;;){+do_rseq(&rseq_lock,rseq_state,cpu,result,targetptr,newval,+{+if(unlikely(lock->c[cpu].v)){+result=false;+}else{+newval=1;+targetptr=(intptr_t*)&lock->c[cpu].v;+}+});+if(likely(result))+break;+}+/*+*Acquiresemanticwhentakinglockaftercontroldependency.+*Matchessmp_store_release().+*/+smp_acquire__after_ctrl_dep();+returncpu;+}++voidrseq_percpu_unlock(structpercpu_lock*lock,intcpu)+{+assert(lock->c[cpu].v==1);+/*+*Releaselock,withreleasesemantic.Matches+*smp_acquire__after_ctrl_dep().+*/+smp_store_release(&lock->c[cpu].v,0);+}++void*test_percpu_spinlock_thread(void*arg)+{+structspinlock_test_data*data=arg;+inti,cpu;++if(rseq_init_current_thread())+abort();+for(i=0;i<data->reps;i++){+cpu=rseq_percpu_lock(&data->lock);+data->c[cpu].count++;+rseq_percpu_unlock(&data->lock,cpu);+}++returnNULL;+}++/*+*Asimpletestwhichimplementsashardedcounterusingaper-cpu+*lock.Obviouslyrealapplicationsmightprefertosimplyusea+*per-cpuincrement;however,thisisreasonableforatestandthe+*lockcanbeextendedtosynchronizemorecomplicatedoperations.+*/+voidtest_percpu_spinlock(void)+{+constintnum_threads=200;+inti,sum;+pthread_ttest_threads[num_threads];+structspinlock_test_datadata;++memset(&data,0,sizeof(data));+data.reps=5000;++for(i=0;i<num_threads;i++)+pthread_create(&test_threads[i],NULL,+test_percpu_spinlock_thread,&data);++for(i=0;i<num_threads;i++)+pthread_join(test_threads[i],NULL);++sum=0;+for(i=0;i<CPU_SETSIZE;i++)+sum+=data.c[i].count;++assert(sum==data.reps*num_threads);+}++intpercpu_list_push(structpercpu_list*list,structpercpu_list_node*node)+{+structrseq_staterseq_state;+intptr_t*targetptr,newval;+intcpu;+boolresult;++do_rseq(&rseq_lock,rseq_state,cpu,result,targetptr,newval,+{+newval=(intptr_t)node;+targetptr=(intptr_t*)&list->c[cpu].head;+node->next=list->c[cpu].head;+});++returncpu;+}++/*+*Unlikeatraditionallock-lesslinkedlist;theavailabilityofa+*rseqprimitiveallowsustoimplementpopwithoutconcernsover+*ABA-typeraces.+*/+structpercpu_list_node*percpu_list_pop(structpercpu_list*list)+{+structpercpu_list_node*head,*next;+structrseq_staterseq_state;+intptr_t*targetptr,newval;+intcpu;+boolresult;++do_rseq(&rseq_lock,rseq_state,cpu,result,targetptr,newval,+{+head=list->c[cpu].head;+if(!head){+result=false;+}else{+next=head->next;+newval=(intptr_t)next;+targetptr=(intptr_t*)&list->c[cpu].head;+}+});++returnhead;+}++void*test_percpu_list_thread(void*arg)+{+inti;+structpercpu_list*list=(structpercpu_list*)arg;++if(rseq_init_current_thread())+abort();++for(i=0;i<100000;i++){+structpercpu_list_node*node=percpu_list_pop(list);++sched_yield();/* encourage shuffling */+if(node)+percpu_list_push(list,node);+}++returnNULL;+}++/* Simultaneous modification to a per-cpu linked list from many threads. */+voidtest_percpu_list(void)+{+inti,j;+longsum=0,expected_sum=0;+structpercpu_listlist;+pthread_ttest_threads[200];+cpu_set_tallowed_cpus;++memset(&list,0,sizeof(list));++/* Generate list entries for every usable cpu. */+sched_getaffinity(0,sizeof(allowed_cpus),&allowed_cpus);+for(i=0;i<CPU_SETSIZE;i++){+if(!CPU_ISSET(i,&allowed_cpus))+continue;+for(j=1;j<=100;j++){+structpercpu_list_node*node;++expected_sum+=j;++node=malloc(sizeof(*node));+assert(node);+node->data=j;+node->next=list.c[i].head;+list.c[i].head=node;+}+}++for(i=0;i<200;i++)+assert(pthread_create(&test_threads[i],NULL,+test_percpu_list_thread,&list)==0);++for(i=0;i<200;i++)+pthread_join(test_threads[i],NULL);++for(i=0;i<CPU_SETSIZE;i++){+cpu_set_tpin_mask;+structpercpu_list_node*node;++if(!CPU_ISSET(i,&allowed_cpus))+continue;++CPU_ZERO(&pin_mask);+CPU_SET(i,&pin_mask);+sched_setaffinity(0,sizeof(pin_mask),&pin_mask);++while((node=percpu_list_pop(&list))){+sum+=node->data;+free(node);+}+}++/*+*Allentriesshouldnowbeaccountedfor(unlesssomeexternal+*actorisinterferingwithourallowedaffinitywhilethis+*testisrunning).+*/+assert(sum==expected_sum);+}++intmain(intargc,char**argv)+{+if(rseq_init_lock(&rseq_lock)){+perror("rseq_init_lock");+return-1;+}+if(rseq_init_current_thread())+gotoerror;+printf("spinlock\n");+test_percpu_spinlock();+printf("percpu_list\n");+test_percpu_list();++if(rseq_destroy_lock(&rseq_lock)){+perror("rseq_destroy_lock");+return-1;+}+return0;++error:+if(rseq_destroy_lock(&rseq_lock))+perror("rseq_destroy_lock");+return-1;+}+
@@ -0,0 +1,106 @@+/*+*Basictestcoverageforcriticalregionsandrseq_current_cpu().+*/++#define _GNU_SOURCE+#include<assert.h>+#include<sched.h>+#include<signal.h>+#include<stdio.h>+#include<string.h>+#include<sys/time.h>++#include"rseq.h"++volatileintsignals_delivered;+volatile__threadstructrseq_statesigtest_start;+staticstructrseq_lockrseq_lock;++voidtest_cpu_pointer(void)+{+cpu_set_taffinity,test_affinity;+inti;++sched_getaffinity(0,sizeof(affinity),&affinity);+CPU_ZERO(&test_affinity);+for(i=0;i<CPU_SETSIZE;i++){+if(CPU_ISSET(i,&affinity)){+CPU_SET(i,&test_affinity);+sched_setaffinity(0,sizeof(test_affinity),+&test_affinity);+assert(rseq_current_cpu()==sched_getcpu());+assert(rseq_current_cpu()==i);+CPU_CLR(i,&test_affinity);+}+}+sched_setaffinity(0,sizeof(affinity),&affinity);+}++/*+*Thisdependssolelyonsomeenvironmentaleventtriggeringacounter+*increase.+*/+voidtest_critical_section(void)+{+structrseq_statestart;+uint32_tevent_counter;++start=rseq_start(&rseq_lock);+event_counter=start.event_counter;+do{+start=rseq_start(&rseq_lock);+}while(start.event_counter==event_counter);+}++voidtest_signal_interrupt_handler(intsigno)+{+structrseq_statecurrent;++current=rseq_start(&rseq_lock);+/*+*Thepotentialcriticalsectionborderedby'start'mustbe+*invalid.+*/+assert(current.event_counter!=sigtest_start.event_counter);+signals_delivered++;+}++voidtest_signal_interrupts(void)+{+structitimervalit={{0,1},{0,1}};++setitimer(ITIMER_PROF,&it,NULL);+signal(SIGPROF,test_signal_interrupt_handler);++do{+sigtest_start=rseq_start(&rseq_lock);+}while(signals_delivered<10);+setitimer(ITIMER_PROF,NULL,NULL);+}++intmain(intargc,char**argv)+{+if(rseq_init_lock(&rseq_lock)){+perror("rseq_init_lock");+return-1;+}+if(rseq_init_current_thread())+gotoinit_thread_error;+printf("testing current cpu\n");+test_cpu_pointer();+printf("testing critical section\n");+test_critical_section();+printf("testing critical section is interrupted by signal\n");+test_signal_interrupts();++if(rseq_destroy_lock(&rseq_lock)){+perror("rseq_destroy_lock");+return-1;+}+return0;++init_thread_error:+if(rseq_destroy_lock(&rseq_lock))+perror("rseq_destroy_lock");+return-1;+}
@@ -0,0 +1,707 @@+#define _GNU_SOURCE+#include<assert.h>+#include<pthread.h>+#include<sched.h>+#include<stdint.h>+#include<stdio.h>+#include<stdlib.h>+#include<string.h>+#include<syscall.h>+#include<unistd.h>+#include<poll.h>+#include<sys/types.h>+#include<signal.h>+#include<errno.h>++staticinlinepid_tgettid(void)+{+returnsyscall(__NR_gettid);+}++#define NR_INJECT 9+staticintloop_cnt[NR_INJECT+1];++staticintopt_modulo;++staticintopt_yield,opt_signal,opt_sleep,opt_fallback_cnt=3,+opt_disable_rseq,opt_threads=200,+opt_reps=5000,opt_disable_mod=0,opt_test='s';++static__threadunsignedintsignals_delivered;++staticstructrseq_lockrseq_lock;++#ifndef BENCHMARK++static__threadunsignedintyield_mod_cnt,nr_retry;++#define printf_nobench(fmt, ...) printf(fmt, ## __VA_ARGS__)++#define RSEQ_INJECT_INPUT \+,[loop_cnt_1]"m"(loop_cnt[1])\+,[loop_cnt_2]"m"(loop_cnt[2])\+,[loop_cnt_3]"m"(loop_cnt[3])\+,[loop_cnt_4]"m"(loop_cnt[4])++#if defined(__x86_64__) || defined(__i386__)++#define INJECT_ASM_REG "eax"++#define RSEQ_INJECT_CLOBBER \+,INJECT_ASM_REG++#define RSEQ_INJECT_ASM(n) \+"mov %[loop_cnt_"#n"], %%"INJECT_ASM_REG"\n\t"\+"test %%"INJECT_ASM_REG",%%"INJECT_ASM_REG"\n\t"\+"jz 333f\n\t"\+"222:\n\t"\+"dec %%"INJECT_ASM_REG"\n\t"\+"jnz 222b\n\t"\+"333:\n\t"++#elif defined(__ARMEL__)++#define INJECT_ASM_REG "r4"++#define RSEQ_INJECT_CLOBBER \+,INJECT_ASM_REG++#define RSEQ_INJECT_ASM(n) \+"ldr "INJECT_ASM_REG", %[loop_cnt_"#n"]\n\t"\+"cmp "INJECT_ASM_REG", #0\n\t"\+"beq 333f\n\t"\+"222:\n\t"\+"subs "INJECT_ASM_REG", #1\n\t"\+"bne 222b\n\t"\+"333:\n\t"++#else+#error unsupported target+#endif++#define RSEQ_INJECT_FAILED \+nr_retry++;++#define RSEQ_INJECT_C(n) \+{\+intloc_i,loc_nr_loops=loop_cnt[n];\+\+for(loc_i=0;loc_i<loc_nr_loops;loc_i++){\+barrier();\+}\+if(loc_nr_loops==-1&&opt_modulo){\+if(yield_mod_cnt==opt_modulo-1){\+if(opt_sleep>0)\+poll(NULL,0,opt_sleep);\+if(opt_yield)\+sched_yield();\+if(opt_signal)\+raise(SIGUSR1);\+yield_mod_cnt=0;\+}else{\+yield_mod_cnt++;\+}\+}\+}++#define RSEQ_FALLBACK_CNT \+opt_fallback_cnt++#else++#define printf_nobench(fmt, ...)++#endif /* BENCHMARK */++#include"rseq.h"++structpercpu_lock_entry{+intptr_tv;+}__attribute__((aligned(128)));++structpercpu_lock{+structpercpu_lock_entryc[CPU_SETSIZE];+};++structtest_data_entry{+intcount;+}__attribute__((aligned(128)));++structspinlock_test_data{+structpercpu_locklock;+structtest_data_entryc[CPU_SETSIZE];+};++structspinlock_thread_test_data{+structspinlock_test_data*data;+intreps;+intreg;+};++structinc_test_data{+structtest_data_entryc[CPU_SETSIZE];+};++structinc_thread_test_data{+structinc_test_data*data;+intreps;+intreg;+};++structpercpu_list_node{+intptr_tdata;+structpercpu_list_node*next;+};++structpercpu_list_entry{+structpercpu_list_node*head;+}__attribute__((aligned(128)));++structpercpu_list{+structpercpu_list_entryc[CPU_SETSIZE];+};++/* A simple percpu spinlock. Returns the cpu lock was acquired on. */+staticintrseq_percpu_lock(structpercpu_lock*lock)+{+structrseq_staterseq_state;+intptr_t*targetptr,newval;+intcpu;+boolresult;++for(;;){+do_rseq(&rseq_lock,rseq_state,cpu,result,targetptr,newval,+{+if(unlikely(lock->c[cpu].v)){+result=false;+}else{+newval=1;+targetptr=(intptr_t*)&lock->c[cpu].v;+}+});+if(likely(result))+break;+}+/*+*Acquiresemanticwhentakinglockaftercontroldependency.+*Matchessmp_store_release().+*/+smp_acquire__after_ctrl_dep();+returncpu;+}++staticvoidrseq_percpu_unlock(structpercpu_lock*lock,intcpu)+{+assert(lock->c[cpu].v==1);+/*+*Releaselock,withreleasesemantic.Matches+*smp_acquire__after_ctrl_dep().+*/+smp_store_release(&lock->c[cpu].v,0);+}++void*test_percpu_spinlock_thread(void*arg)+{+structspinlock_thread_test_data*thread_data=arg;+structspinlock_test_data*data=thread_data->data;+inti,cpu;++if(!opt_disable_rseq&&thread_data->reg+&&rseq_init_current_thread())+abort();+for(i=0;i<thread_data->reps;i++){+cpu=rseq_percpu_lock(&data->lock);+data->c[cpu].count++;+rseq_percpu_unlock(&data->lock,cpu);+#ifndef BENCHMARK+if(i!=0&&!(i%(thread_data->reps/10)))+printf("tid %d: count %d\n",(int)gettid(),i);+#endif+}+printf_nobench("tid %d: number of retry: %d, signals delivered: %u, nr_fallback %u, nr_fallback_wait %u\n",+(int)gettid(),nr_retry,signals_delivered,+__rseq_thread_state.fallback_cnt,+__rseq_thread_state.fallback_wait_cnt);+returnNULL;+}++/*+*Asimpletestwhichimplementsashardedcounterusingaper-cpu+*lock.Obviouslyrealapplicationsmightprefertosimplyusea+*per-cpuincrement;however,thisisreasonableforatestandthe+*lockcanbeextendedtosynchronizemorecomplicatedoperations.+*/+voidtest_percpu_spinlock(void)+{+constintnum_threads=opt_threads;+inti,sum,ret;+pthread_ttest_threads[num_threads];+structspinlock_test_datadata;+structspinlock_thread_test_datathread_data[num_threads];++memset(&data,0,sizeof(data));+for(i=0;i<num_threads;i++){+thread_data[i].reps=opt_reps;+if(opt_disable_mod<=0||(i%opt_disable_mod))+thread_data[i].reg=1;+else+thread_data[i].reg=0;+thread_data[i].data=&data;+ret=pthread_create(&test_threads[i],NULL,+test_percpu_spinlock_thread,&thread_data[i]);+if(ret){+errno=ret;+perror("pthread_create");+abort();+}+}++for(i=0;i<num_threads;i++){+pthread_join(test_threads[i],NULL);+if(ret){+errno=ret;+perror("pthread_join");+abort();+}+}++sum=0;+for(i=0;i<CPU_SETSIZE;i++)+sum+=data.c[i].count;++assert(sum==opt_reps*num_threads);+}++void*test_percpu_inc_thread(void*arg)+{+structinc_thread_test_data*thread_data=arg;+structinc_test_data*data=thread_data->data;+inti;++if(!opt_disable_rseq&&thread_data->reg+&&rseq_init_current_thread())+abort();+for(i=0;i<thread_data->reps;i++){+structrseq_staterseq_state;+intptr_t*targetptr,newval;+intcpu;+boolresult;++do_rseq(&rseq_lock,rseq_state,cpu,result,targetptr,newval,+{+newval=(intptr_t)data->c[cpu].count+1;+targetptr=(intptr_t*)&data->c[cpu].count;+});++#ifndef BENCHMARK+if(i!=0&&!(i%(thread_data->reps/10)))+printf("tid %d: count %d\n",(int)gettid(),i);+#endif+}+printf_nobench("tid %d: number of retry: %d, signals delivered: %u, nr_fallback %u, nr_fallback_wait %u\n",+(int)gettid(),nr_retry,signals_delivered,+__rseq_thread_state.fallback_cnt,+__rseq_thread_state.fallback_wait_cnt);+returnNULL;+}++voidtest_percpu_inc(void)+{+constintnum_threads=opt_threads;+inti,sum,ret;+pthread_ttest_threads[num_threads];+structinc_test_datadata;+structinc_thread_test_datathread_data[num_threads];++memset(&data,0,sizeof(data));+for(i=0;i<num_threads;i++){+thread_data[i].reps=opt_reps;+if(opt_disable_mod<=0||(i%opt_disable_mod))+thread_data[i].reg=1;+else+thread_data[i].reg=0;+thread_data[i].data=&data;+ret=pthread_create(&test_threads[i],NULL,+test_percpu_inc_thread,&thread_data[i]);+if(ret){+errno=ret;+perror("pthread_create");+abort();+}+}++for(i=0;i<num_threads;i++){+pthread_join(test_threads[i],NULL);+if(ret){+errno=ret;+perror("pthread_join");+abort();+}+}++sum=0;+for(i=0;i<CPU_SETSIZE;i++)+sum+=data.c[i].count;++assert(sum==opt_reps*num_threads);+}++intpercpu_list_push(structpercpu_list*list,structpercpu_list_node*node)+{+structrseq_staterseq_state;+intptr_t*targetptr,newval;+intcpu;+boolresult;++do_rseq(&rseq_lock,rseq_state,cpu,result,targetptr,newval,+{+newval=(intptr_t)node;+targetptr=(intptr_t*)&list->c[cpu].head;+node->next=list->c[cpu].head;+});++returncpu;+}++/*+*Unlikeatraditionallock-lesslinkedlist;theavailabilityofa+*rseqprimitiveallowsustoimplementpopwithoutconcernsover+*ABA-typeraces.+*/+structpercpu_list_node*percpu_list_pop(structpercpu_list*list)+{+structpercpu_list_node*head,*next;+structrseq_staterseq_state;+intptr_t*targetptr,newval;+intcpu;+boolresult;++do_rseq(&rseq_lock,rseq_state,cpu,result,targetptr,newval,+{+head=list->c[cpu].head;+if(!head){+result=false;+}else{+next=head->next;+newval=(intptr_t)next;+targetptr=(intptr_t*)&list->c[cpu].head;+}+});++returnhead;+}++void*test_percpu_list_thread(void*arg)+{+inti;+structpercpu_list*list=(structpercpu_list*)arg;++if(rseq_init_current_thread())+abort();++for(i=0;i<opt_reps;i++){+structpercpu_list_node*node=percpu_list_pop(list);++if(opt_yield)+sched_yield();/* encourage shuffling */+if(node)+percpu_list_push(list,node);+}++returnNULL;+}++/* Simultaneous modification to a per-cpu linked list from many threads. */+voidtest_percpu_list(void)+{+constintnum_threads=opt_threads;+inti,j,ret;+longsum=0,expected_sum=0;+structpercpu_listlist;+pthread_ttest_threads[num_threads];+cpu_set_tallowed_cpus;++memset(&list,0,sizeof(list));++/* Generate list entries for every usable cpu. */+sched_getaffinity(0,sizeof(allowed_cpus),&allowed_cpus);+for(i=0;i<CPU_SETSIZE;i++){+if(!CPU_ISSET(i,&allowed_cpus))+continue;+for(j=1;j<=100;j++){+structpercpu_list_node*node;++expected_sum+=j;++node=malloc(sizeof(*node));+assert(node);+node->data=j;+node->next=list.c[i].head;+list.c[i].head=node;+}+}++for(i=0;i<num_threads;i++){+ret=pthread_create(&test_threads[i],NULL,+test_percpu_list_thread,&list);+if(ret){+errno=ret;+perror("pthread_create");+abort();+}+}++for(i=0;i<num_threads;i++){+pthread_join(test_threads[i],NULL);+if(ret){+errno=ret;+perror("pthread_join");+abort();+}+}++for(i=0;i<CPU_SETSIZE;i++){+cpu_set_tpin_mask;+structpercpu_list_node*node;++if(!CPU_ISSET(i,&allowed_cpus))+continue;++CPU_ZERO(&pin_mask);+CPU_SET(i,&pin_mask);+sched_setaffinity(0,sizeof(pin_mask),&pin_mask);++while((node=percpu_list_pop(&list))){+sum+=node->data;+free(node);+}+}++/*+*Allentriesshouldnowbeaccountedfor(unlesssomeexternal+*actorisinterferingwithourallowedaffinitywhilethis+*testisrunning).+*/+assert(sum==expected_sum);+}++staticvoidtest_signal_interrupt_handler(intsigno)+{+signals_delivered++;+}++staticintset_signal_handler(void)+{+intret=0;+structsigactionsa;+sigset_tsigset;++ret=sigemptyset(&sigset);+if(ret<0){+perror("sigemptyset");+returnret;+}++sa.sa_handler=test_signal_interrupt_handler;+sa.sa_mask=sigset;+sa.sa_flags=0;+ret=sigaction(SIGUSR1,&sa,NULL);+if(ret<0){+perror("sigaction");+returnret;+}++printf_nobench("Signal handler set for SIGUSR1\n");++returnret;+}++staticvoidshow_usage(intargc,char**argv)+{+printf("Usage : %s <OPTIONS>\n",+argv[0]);+printf("OPTIONS:\n");+printf(" [-1 loops] Number of loops for delay injection 1\n");+printf(" [-2 loops] Number of loops for delay injection 2\n");+printf(" [-3 loops] Number of loops for delay injection 3\n");+printf(" [-4 loops] Number of loops for delay injection 4\n");+printf(" [-5 loops] Number of loops for delay injection 5 (-1 to enable -m)\n");+printf(" [-6 loops] Number of loops for delay injection 6 (-1 to enable -m)\n");+printf(" [-7 loops] Number of loops for delay injection 7 (-1 to enable -m)\n");+printf(" [-8 loops] Number of loops for delay injection 8 (-1 to enable -m)\n");+printf(" [-9 loops] Number of loops for delay injection 9 (-1 to enable -m)\n");+printf(" [-m N] Yield/sleep/kill every modulo N (default 0: disabled) (>= 0)\n");+printf(" [-y] Yield\n");+printf(" [-k] Kill thread with signal\n");+printf(" [-s S] S: =0: disabled (default), >0: sleep time (ms)\n");+printf(" [-f N] Use fallback every N failure (>= 1)\n");+printf(" [-t N] Number of threads (default 200)\n");+printf(" [-r N] Number of repetitions per thread (default 5000)\n");+printf(" [-d] Disable rseq system call (no initialization)\n");+printf(" [-D M] Disable rseq for each M threads\n");+printf(" [-T test] Choose test: (s)pinlock, (l)ist, (i)ncrement\n");+printf(" [-h] Show this help.\n");+printf("\n");+}++intmain(intargc,char**argv)+{+inti;++if(rseq_init_lock(&rseq_lock)){+perror("rseq_init_lock");+return-1;+}+if(set_signal_handler())+gotoerror;+for(i=1;i<argc;i++){+if(argv[i][0]!='-')+continue;+switch(argv[i][1]){+case'1':+case'2':+case'3':+case'4':+case'5':+case'6':+case'7':+case'8':+case'9':+if(argc<i+2){+show_usage(argc,argv);+gotoerror;+}+loop_cnt[argv[i][1]-'0']=atol(argv[i+1]);+i++;+break;+case'm':+if(argc<i+2){+show_usage(argc,argv);+gotoerror;+}+opt_modulo=atol(argv[i+1]);+if(opt_modulo<0){+show_usage(argc,argv);+gotoerror;+}+i++;+break;+case's':+if(argc<i+2){+show_usage(argc,argv);+gotoerror;+}+opt_sleep=atol(argv[i+1]);+if(opt_sleep<0){+show_usage(argc,argv);+gotoerror;+}+i++;+break;+case'y':+opt_yield=1;+break;+case'k':+opt_signal=1;+break;+case'd':+opt_disable_rseq=1;+break;+case'D':+if(argc<i+2){+show_usage(argc,argv);+gotoerror;+}+opt_disable_mod=atol(argv[i+1]);+if(opt_disable_mod<0){+show_usage(argc,argv);+gotoerror;+}+i++;+break;+case'f':+if(argc<i+2){+show_usage(argc,argv);+gotoerror;+}+opt_fallback_cnt=atol(argv[i+1]);+if(opt_fallback_cnt<1){+show_usage(argc,argv);+gotoerror;+}+i++;+break;+case't':+if(argc<i+2){+show_usage(argc,argv);+gotoerror;+}+opt_threads=atol(argv[i+1]);+if(opt_threads<0){+show_usage(argc,argv);+gotoerror;+}+i++;+break;+case'r':+if(argc<i+2){+show_usage(argc,argv);+gotoerror;+}+opt_reps=atol(argv[i+1]);+if(opt_reps<0){+show_usage(argc,argv);+gotoerror;+}+i++;+break;+case'h':+show_usage(argc,argv);+gotoend;+case'T':+if(argc<i+2){+show_usage(argc,argv);+gotoerror;+}+opt_test=*argv[i+1];+switch(opt_test){+case's':+case'l':+case'i':+break;+default:+show_usage(argc,argv);+gotoerror;+}+i++;+break;+default:+show_usage(argc,argv);+gotoerror;+}+}++if(!opt_disable_rseq&&rseq_init_current_thread())+gotoerror;+switch(opt_test){+case's':+printf_nobench("spinlock\n");+test_percpu_spinlock();+break;+case'l':+printf_nobench("linked list\n");+test_percpu_list();+break;+case'i':+printf_nobench("counter increment\n");+test_percpu_inc();+break;+}+end:+return0;++error:+if(rseq_destroy_lock(&rseq_lock))+perror("rseq_destroy_lock");+return-1;+}
From: Andy Lutomirski <luto@amacapital.net> Date: 2016-07-25 23:02:46
On Thu, Jul 21, 2016 at 2:14 PM, Mathieu Desnoyers
[off-list ref] wrote:
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, int flags);
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.
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 can be used to check whether rseq is registered for the
current thread.
The layout of struct rseq is as follows:
Structure alignment
This structure needs to be aligned on multiples of 64
bytes.
Structure size
This structure has a fixed size of 128 bytes.
Fields
cpu_id
Cache of the CPU number on which the calling thread is
running.
event_counter
Restartable sequences event_counter field.
That's an unhelpful description.
rseq_cs
Restartable sequences rseq_cs field. Points to a struct
rseq_cs.
Why is it a pointer?
The layout of struct rseq_cs is as follows:
Structure alignment
This structure needs to be aligned on multiples of 64
bytes.
Structure size
This structure has a fixed size of 192 bytes.
Fields
start_ip
Instruction pointer address of the first instruction of
the sequence of consecutive assembly instructions.
post_commit_ip
Instruction pointer 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 flags argument is currently unused and must be specified as
0.
Typically, a library or application will keep the rseq struc‐
ture in a thread-local storage variable, or other memory areas
"variable or other memory area"
belonging to each thread. It is recommended to perform volatile
reads of the thread-local cache to prevent the compiler from
doing load tearing. An alternative approach is to read each
field from inline assembly.
I don't think the man page needs to tell people how to implement
correct atomic loads.
Each thread is responsible for registering its rseq structure.
Only one rseq structure address can be registered per thread.
Once set, the rseq address is idempotent for a given thread.
"Idempotent" is a property that applies to an action, and the "rseq
address" is not an action. I don't know what you're trying to say.
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 single-copy atomicity semantics, which guarantee
that other threads performing single-copy atomic reads of the
cpu number cache will always observe a consistent value.
s/single-copy/relaxed atomic/ perhaps?
Memory registered as rseq structure should never be deallocated
before the thread which registered it exits: specifically, it
should not be freed, and the library containing the registered
thread-local storage should not be dlclose'd. Violating this
constraint may cause a SIGSEGV signal to be delivered to the
thread.
That's an unfortunate constraint for threads that exit without help.
Unregistration of associated rseq structure is implicitly per‐
formed when a thread or process exit.
exits.
[...]
Can you please document what this thing does prior to giving an
example of how to use it.
Hmm, here are the docs, sort of:
+/*
+ * Each restartable sequence assembly block defines a "struct rseq_cs"
+ * structure which describes the post_commit_ip address, and the
+ * abort_ip address where the kernel should move the thread instruction
+ * pointer if a rseq critical section assembly block is preempted or if
+ * a signal is delivered on top of a rseq critical section assembly
+ * block. It also contains a start_ip, which is the address of the start
+ * of the rseq assembly block, which is useful to debuggers.
+ *
+ * The algorithm for a restartable sequence assembly block is as
+ * follows:
+ *
+ * rseq_start()
+ *
+ * 0. Userspace loads the current event counter value from the
+ * event_counter field of the registered struct rseq TLS area,
+ *
+ * rseq_finish()
+ *
+ * Steps [1]-[3] (inclusive) need to be a sequence of instructions in
+ * userspace that can handle being moved to the abort_ip between any
+ * of those instructions.
+ *
+ * The abort_ip address needs to be equal or above the post_commit_ip.
+ * Step [4] and the failure code step [F1] need to be at addresses
+ * equal or above the post_commit_ip.
+ *
+ * 1. Userspace stores the address of the struct rseq cs rseq
"struct rseq cs rseq" contains a typo.
+ * assembly block descriptor into the rseq_cs field of the
+ * registered struct rseq TLS area.
+ *
+ * 2. Userspace tests to see whether the current event counter values
+ * match those loaded at [0]. Manually jumping to [F1] in case of
+ * a mismatch.
Grammar issues here. More importantly, you said "values", but you
only described one value.
+ *
+ * Note that if we are preempted or interrupted by a signal
+ * after [1] and before post_commit_ip, then the kernel also
+ * performs the comparison performed in [2], and conditionally
+ * clears rseq_cs, then jumps us to abort_ip.
This is the first I've heard of rseq_cs being something that gets
changed as a result of using this facility. What code sets it in the
first place?
I think you've also mentioned "preemption" and "migration". Which do you mean?
+ *
+ * 3. Userspace critical section final instruction before
+ * post_commit_ip is the commit. The critical section is
+ * self-terminating.
+ * [post_commit_ip]
+ *
+ * 4. Userspace clears the rseq_cs field of the struct rseq
+ * TLS area.
+ *
+ * 5. Return true.
+ *
+ * On failure at [2]:
+ *
A major issue I have with percpu critical sections or rseqs or
whatever you want to call them is that, every time I talk to someone
about them, there are a different set of requirements that they are
supposed to satisfy. So:
What problem does this solve?
What are its atomicity properties? Under what conditions does it
work? What assumptions does it make?
What real-world operations become faster as a result of rseq (as
opposed to just cpu number queries)?
Why is it important for the kernel to do something special on every preemption?
What "events" does "event_counter" count and why?
If I'm understanding the intent of this code correctly (which is a big
if), I think you're trying to do this:
start a critical section;
compute something;
commit;
if (commit worked)
return;
else
try again;
where "commit;" is a single instruction. The kernel guarantees that
if the thread is preempted (or migrated, perhaps?) between the start
and commit steps then commit will be forced to fail (or be skipped
entirely). Because I don't understand what you're doing with this
primitive, I can't really tell why you need to detect preemption as
opposed to just migration.
For example: would the following primitive solve the same problem?
begin_dont_migrate_me()
figure out what store to do to take the percpu lock;
do that store;
if (end_dont_migrate_me())
return;
// oops, the kernel migrated us. retry.
--Andy
----- On Jul 25, 2016, at 7:02 PM, Andy Lutomirski luto-kltTT9wpgjJwATOyAt5JVQ@public.gmane.org wrote:
On Thu, Jul 21, 2016 at 2:14 PM, Mathieu Desnoyers
[off-list ref] wrote:
quoted
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, int flags);
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.
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 can be used to check whether rseq is registered for the
current thread.
The layout of struct rseq is as follows:
Structure alignment
This structure needs to be aligned on multiples of 64
bytes.
Structure size
This structure has a fixed size of 128 bytes.
Fields
cpu_id
Cache of the CPU number on which the calling thread is
running.
event_counter
Restartable sequences event_counter field.
That's an unhelpful description.
Good point, how about:
event_counter
Counter guaranteed to be incremented when the current thread is
preempted or when a signal is delivered to the current thread.
In that same line of thoughts, I would reword cpu_id as:
cpu_id
Cache of the CPU number on which the current thread is
running.
quoted
rseq_cs
Restartable sequences rseq_cs field. Points to a struct
rseq_cs.
Why is it a pointer?
Rewording like this should help understand:
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. It is cleared
after the end of the critical section.
quoted
The layout of struct rseq_cs is as follows:
Structure alignment
This structure needs to be aligned on multiples of 64
bytes.
Structure size
This structure has a fixed size of 192 bytes.
Fields
start_ip
Instruction pointer address of the first instruction of
the sequence of consecutive assembly instructions.
post_commit_ip
Instruction pointer 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 flags argument is currently unused and must be specified as
0.
Typically, a library or application will keep the rseq struc‐
ture in a thread-local storage variable, or other memory areas
"variable or other memory area"
ok
quoted
belonging to each thread. It is recommended to perform volatile
reads of the thread-local cache to prevent the compiler from
doing load tearing. An alternative approach is to read each
field from inline assembly.
I don't think the man page needs to tell people how to implement
correct atomic loads.
ok, I can remove the two previous sentences.
quoted
Each thread is responsible for registering its rseq structure.
Only one rseq structure address can be registered per thread.
Once set, the rseq address is idempotent for a given thread.
"Idempotent" is a property that applies to an action, and the "rseq
address" is not an action. I don't know what you're trying to say.
I mean there is only one address registered per thread, and it stays
registered for the life-time of the thread. Perhaps I could say:
"Once set, the rseq address never changes for a given thread."
quoted
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 single-copy atomicity semantics, which guarantee
that other threads performing single-copy atomic reads of the
cpu number cache will always observe a consistent value.
s/single-copy/relaxed atomic/ perhaps?
ok
quoted
Memory registered as rseq structure should never be deallocated
before the thread which registered it exits: specifically, it
should not be freed, and the library containing the registered
thread-local storage should not be dlclose'd. Violating this
constraint may cause a SIGSEGV signal to be delivered to the
thread.
That's an unfortunate constraint for threads that exit without help.
I don't understand what you are pointing at here. I see this mostly as
a constraint on the life-time of the library that holds the struct rseq
TLS more than a constraint on the thread life-time.
quoted
Unregistration of associated rseq structure is implicitly per‐
formed when a thread or process exit.
exits.
ok
[...]
Can you please document what this thing does prior to giving an
example of how to use it.
Good point, will do. (more comments on what can be added as documentation
below)
+/*
+ * Each restartable sequence assembly block defines a "struct rseq_cs"
+ * structure which describes the post_commit_ip address, and the
+ * abort_ip address where the kernel should move the thread instruction
+ * pointer if a rseq critical section assembly block is preempted or if
+ * a signal is delivered on top of a rseq critical section assembly
+ * block. It also contains a start_ip, which is the address of the start
+ * of the rseq assembly block, which is useful to debuggers.
+ *
+ * The algorithm for a restartable sequence assembly block is as
+ * follows:
+ *
+ * rseq_start()
+ *
+ * 0. Userspace loads the current event counter value from the
+ * event_counter field of the registered struct rseq TLS area,
+ *
+ * rseq_finish()
+ *
+ * Steps [1]-[3] (inclusive) need to be a sequence of instructions in
+ * userspace that can handle being moved to the abort_ip between any
+ * of those instructions.
+ *
+ * The abort_ip address needs to be equal or above the post_commit_ip.
+ * Step [4] and the failure code step [F1] need to be at addresses
+ * equal or above the post_commit_ip.
+ *
+ * 1. Userspace stores the address of the struct rseq cs rseq
"struct rseq cs rseq" contains a typo.
should be "struct rseq_cs"
quoted
+ * assembly block descriptor into the rseq_cs field of the
+ * registered struct rseq TLS area.
+ *
+ * 2. Userspace tests to see whether the current event counter values
+ * match those loaded at [0]. Manually jumping to [F1] in case of
+ * a mismatch.
Grammar issues here. More importantly, you said "values", but you
only described one value.
Indeed, values -> value, and those -> the value
quoted
+ *
+ * Note that if we are preempted or interrupted by a signal
+ * after [1] and before post_commit_ip, then the kernel also
+ * performs the comparison performed in [2], and conditionally
+ * clears rseq_cs, then jumps us to abort_ip.
This is the first I've heard of rseq_cs being something that gets
changed as a result of using this facility. What code sets it in the
first place?
struct rseq_cs (the critical section descriptor) is statically declared,
never changes. What I should clarify above is that the rseq_cs field of
struct rseq gets cleared (not the struct rseq_cs per se).
The struct rseq_cs field is initially at NULL, and is populated by the
struct rseq_cs descriptor address when entering the critical section.
It is set back to NULL right after exiting the critical section, through
both the success and failure paths.
I think you've also mentioned "preemption" and "migration". Which do you mean?
We really care about preemption here. Every migration implies a
preemption from a user-space perspective. If we would only care
about keeping the CPU id up-to-date, hooking into migration would be
enough. But since we want atomicity guarantees for restartable
sequences, we need to hook into preemption.
I should update the changelog of patch 1/7 to specify that we really do
hook on preemption, even for the cpu_id update part.
quoted
+ *
+ * 3. Userspace critical section final instruction before
+ * post_commit_ip is the commit. The critical section is
+ * self-terminating.
+ * [post_commit_ip]
+ *
+ * 4. Userspace clears the rseq_cs field of the struct rseq
+ * TLS area.
+ *
+ * 5. Return true.
+ *
+ * On failure at [2]:
+ *
A major issue I have with percpu critical sections or rseqs or
whatever you want to call them is that, every time I talk to someone
about them, there are a different set of requirements that they are
supposed to satisfy. So:
What problem does this solve?
It allows user-space to perform update operations on per-cpu data without
requiring heavy-weight atomic operations.
What are its atomicity properties? Under what conditions does it
work? What assumptions does it make?
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.
What real-world operations become faster as a result of rseq (as
opposed to just cpu number queries)?
A few examples of operations accelerated:
- incrementing per-cpu counters,
- per-cpu spin-lock,
- per-cpu linked-lists (including memory allocator free-list),
- per-cpu ring buffer,
Perhaps others will have other operations in mind ?
Note that compared to Paul Turner's patchset, I removed the percpu_cmpxchg
and percpu_cmpxchg_check APIs from the test program rseq.h in user-space,
because I found out that it was difficult to guarantee progress with those
APIs. The do_rseq() approach, which does 2 attempts and falls back to
locking, does provide progress guarantees even in the face of (unlikely)
frequent migrations.
Why is it important for the kernel to do something special on every preemption?
This is how we can ensure that the entire critical section,
consisting of both the C part and the assembly instruction
sequence, will issue the commit instruction only if executed
atomically with respect to other threads scheduled on the
same CPU.
What "events" does "event_counter" count and why?
Technically, it increments each time a thread returns to
user-space with the NOTIFY_RESUME thread flag set. We ensure
to set this flag on preemption (out), as well as signal delivery.
So it is guaranteed to increment when either of those events take
place. It can however increment due to other kernel code setting
TIF_NOTIFY_RESUME before returning to user-space.
It is meant to allow user-space to detect preemption and signal
delivery, not to count the exact number of such events.
If I'm understanding the intent of this code correctly (which is a big
if), I think you're trying to do this:
start a critical section;
compute something;
commit;
if (commit worked)
return;
else
try again;
where "commit;" is a single instruction. The kernel guarantees that
if the thread is preempted (or migrated, perhaps?)
A thread needs to have been preempted in order to be migrated, so
from a user-space perspective, detecting preemption is a super-set
of detecting migration. We track preemption and signal delivery here.
between the start
and commit steps then commit will be forced to fail (or be skipped
entirely). Because I don't understand what you're doing with this
primitive, I can't really tell why you need to detect preemption as
opposed to just migration.
For example: would the following primitive solve the same problem?
begin_dont_migrate_me()
figure out what store to do to take the percpu lock;
do that store;
if (end_dont_migrate_me())
return;
// oops, the kernel migrated us. retry.
First, prohibiting migration from user-space has been frowned upon
by scheduler developers for a long time, and I doubt this mindset will
change.
But if we look at it from the point of view of letting user-space
retry when it detects migration (rather than preemption), it would
require that we use an atomic instruction (although without the lock
prefix) as the commit instruction to ensure atomicity with respect
to other threads running on the same CPU. Detecting preemption
instead allows us to use a simple store instruction as the commit.
Simple store instructions (e.g. mov) are faster than atomic
instructions (e.g. xadd, cmpxchg...). Moreover, detecting
migrations and using atomic instructions as commit is prone to ABA
(e.g. free-list use-case) that are prevented by the restart on
preemption or signal delivery.
Thanks for looking into it!
Mathieu
Hi Mathieu,
On Thu, Jul 21, 2016 at 05:14:16PM -0400, Mathieu Desnoyers wrote:
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)
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
Agreed ;-)
architectures and speeds up the user-space fast path. A locking-based
fall-back, purely implemented in user-space, is proposed here to deal
with debugger single-stepping. This fallback interacts with rseq_start()
and rseq_finish(), which force retries in response to concurrent
lock-based activity.
So I have enabled this on powerpc, thanks to your nice work to make
things easy for porting ;-)
A patchset will follow in-reply-to this email, which includes patches
enabling this on powerpc and a patch that improves the portability of
the selftests, which I think it's not necessary to be a standalone
patch, so it's OK to be merged into your patch #7.
I did some tests on 64bit little/big endian pSeries(guest) kernel with
selftest cases(64bit LE selftest on 64bit LE kernel, 64/32bit BE
selftest on 64bit BE kernel), things seemingly went well ;-)
Here are some benchmark results I got on a little endian guest with 64
VCPUs:
Benchmarking various approaches for reading the current CPU number:
Power8 PSeries Guest(64 VCPUs, the host has 16 cores, 128 hardware
threads):
- Baseline (empty loop): 1.56 ns
- Read CPU from rseq cpu_id: 1.56 ns
- Read CPU from rseq cpu_id (lazy register): 2.08 ns
- glibc 2.23-0ubuntu3 getcpu: 7.72 ns
- getcpu system call: 91.80 ns
Benchmarking various approaches for counter increment:
Power8 PSeries KVM Guest(64 VCPUs, the host has 16 cores, 128 hardware
threads):
Counter increment speed (ns/increment)
1 thread 2 threads 4 threads 8 threads 16 threads 32 threads
global increment (baseline) 6.5 N/A N/A N/A N/A N/A
percpu rseq increment 6.9 6.9 7.2 7.3 15.4 35.5
percpu rseq spinlock 19.0 18.9 19.4 19.4 35.5 71.8
global atomic increment 25.8 111.0 261.0 905.2 2319.5 4170.5 (__sync_add_and_fetch_4)
global atomic CAS 26.2 119.0 341.6 1183.0 3951.3 9312.5 (__sync_val_compare_and_swap_4)
global pthread mutex 40.0 238.1 644.0 2052.2 4272.5 8612.2
I surely need to run more tests for my patches in different
environments, and will try to adjust the patchset according to whatever
change you make(e.g. rseq_finish2) in the future.
(Add PPC maintainers in Cc)
Regards,
Boqun
Here are benchmarks of counter increment in various scenarios compared
to restartable sequences:
ARMv7 Processor rev 4 (v7l)
Machine model: Cubietruck
Counter increment speed (ns/increment)
1 thread 2 threads
global increment (baseline) 6 N/A
percpu rseq increment 50 52
percpu rseq spinlock 94 94
global atomic increment 48 74 (__sync_add_and_fetch_4)
global atomic CAS 50 172 (__sync_val_compare_and_swap_4)
global pthread mutex 148 862
ARMv7 Processor rev 10 (v7l)
Machine model: Wandboard
Counter increment speed (ns/increment)
1 thread 4 threads
global increment (baseline) 7 N/A
percpu rseq increment 50 50
percpu rseq spinlock 82 84
global atomic increment 44 262 (__sync_add_and_fetch_4)
global atomic CAS 46 316 (__sync_val_compare_and_swap_4)
global pthread mutex 146 1400
x86-64 Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz:
Counter increment speed (ns/increment)
1 thread 8 threads
global increment (baseline) 3.0 N/A
percpu rseq increment 3.6 3.8
percpu rseq spinlock 5.6 6.2
global LOCK; inc 8.0 166.4
global LOCK; cmpxchg 13.4 435.2
global pthread mutex 25.2 1363.6
* 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 migration 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
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.
The current semantics of do_resq() is to do a intptr_t type store in
successful cases, however, in test_percpu_{inc,spinlock}, we use
test_data_entry::count as the location to store, whose type is int.
intptr_t and int have different size on LP64 systems, and despite the
inconsistency of types, having test_data_entry::count as int needs more
care on endian handling.
To make things simpler and more consistent, convert
test_data_entry::count to type intptr_t, which also makes the coming
tests for ppc64le and ppc64 share the same code.
Signed-off-by: Boqun Feng <redacted>
---
tools/testing/selftests/rseq/param_test.c | 8 +++++---
1 file changed, 5 insertions(+), 3 deletions(-)
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.
Signed-off-by: Boqun Feng <redacted>
---
arch/powerpc/Kconfig | 1 +
arch/powerpc/kernel/signal.c | 3 +++
2 files changed, 4 insertions(+)
@@ -131,6 +131,8 @@ static void do_signal(struct pt_regs *regs)/* Re-enable the breakpoints for the signal stack */thread_change_pc(current,regs);+rseq_signal_deliver(regs);+if(is32){if(ksig.ka.sa.sa_flags&SA_SIGINFO)ret=handle_rt_signal32(&ksig,oldset,regs);
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.
Signed-off-by: Boqun Feng <redacted>
---
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(-)
As rseq syscall is enabled on PPC, implement the self-tests on PPC to
verify the implementation of the syscall.
Please note we only support 32bit userspace on BE kernel.
Signed-off-by: Boqun Feng <redacted>
---
tools/testing/selftests/rseq/param_test.c | 14 ++++
tools/testing/selftests/rseq/rseq.h | 120 ++++++++++++++++++++++++++++++
2 files changed, 134 insertions(+)
----- On Jul 27, 2016, at 11:05 AM, Boqun Feng boqun.feng@gmail.com wrote:
quoted hunk
As rseq syscall is enabled on PPC, implement the self-tests on PPC to
verify the implementation of the syscall.
Please note we only support 32bit userspace on BE kernel.
Signed-off-by: Boqun Feng <redacted>
---
tools/testing/selftests/rseq/param_test.c | 14 ++++
tools/testing/selftests/rseq/rseq.h | 120 ++++++++++++++++++++++++++++++
2 files changed, 134 insertions(+)
Can you check if defining has_fast_acquire_release() to 0 speeds up
performance significantly ? It turns the smp_lwsync() into a
compiler barrier() on the smp_load_acquire() side (fast-path), and
turn the smp_lwsync() into a membarrier system call instead of the
matching smp_store_release() (slow path).
Thanks,
Mathieu
----- On Jul 27, 2016, at 11:05 AM, Boqun Feng boqun.feng-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org wrote:
The current semantics of do_resq() is to do a intptr_t type store in
successful cases, however, in test_percpu_{inc,spinlock}, we use
test_data_entry::count as the location to store, whose type is int.
intptr_t and int have different size on LP64 systems, and despite the
inconsistency of types, having test_data_entry::count as int needs more
care on endian handling.
To make things simpler and more consistent, convert
test_data_entry::count to type intptr_t, which also makes the coming
tests for ppc64le and ppc64 share the same code.
Folded into my rseq tests patch for next round, thanks!
I also took care of basic_percpu_ops_test.c which had the
same issue.
Thanks!
Mathieu
----- On Jul 27, 2016, at 11:03 AM, Boqun Feng boqun.feng-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org wrote:
Hi Mathieu,
On Thu, Jul 21, 2016 at 05:14:16PM -0400, Mathieu Desnoyers wrote:
quoted
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)
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
Agreed ;-)
quoted
architectures and speeds up the user-space fast path. A locking-based
fall-back, purely implemented in user-space, is proposed here to deal
with debugger single-stepping. This fallback interacts with rseq_start()
and rseq_finish(), which force retries in response to concurrent
lock-based activity.
So I have enabled this on powerpc, thanks to your nice work to make
things easy for porting ;-)
A patchset will follow in-reply-to this email, which includes patches
enabling this on powerpc and a patch that improves the portability of
the selftests, which I think it's not necessary to be a standalone
patch, so it's OK to be merged into your patch #7.
I did some tests on 64bit little/big endian pSeries(guest) kernel with
selftest cases(64bit LE selftest on 64bit LE kernel, 64/32bit BE
selftest on 64bit BE kernel), things seemingly went well ;-)
Here are some benchmark results I got on a little endian guest with 64
VCPUs:
Benchmarking various approaches for reading the current CPU number:
Power8 PSeries Guest(64 VCPUs, the host has 16 cores, 128 hardware
threads):
- Baseline (empty loop): 1.56 ns
- Read CPU from rseq cpu_id: 1.56 ns
- Read CPU from rseq cpu_id (lazy register): 2.08 ns
- glibc 2.23-0ubuntu3 getcpu: 7.72 ns
- getcpu system call: 91.80 ns
Benchmarking various approaches for counter increment:
Power8 PSeries KVM Guest(64 VCPUs, the host has 16 cores, 128 hardware
threads):
Counter increment speed (ns/increment)
1 thread 2 threads 4 threads 8 threads 16 threads 32 threads
global increment (baseline) 6.5 N/A N/A N/A
N/A N/A
percpu rseq increment 6.9 6.9 7.2 7.3
15.4 35.5
percpu rseq spinlock 19.0 18.9 19.4 19.4
35.5 71.8
global atomic increment 25.8 111.0 261.0 905.2
2319.5 4170.5 (__sync_add_and_fetch_4)
global atomic CAS 26.2 119.0 341.6 1183.0
3951.3 9312.5 (__sync_val_compare_and_swap_4)
global pthread mutex 40.0 238.1 644.0 2052.2
4272.5 8612.2
I surely need to run more tests for my patches in different
environments, and will try to adjust the patchset according to whatever
change you make(e.g. rseq_finish2) in the future.
I'm very glad to see it brings speedup on powerpc too! I plan
minor changes following the feedback I already got. I'll surely
grab your updated benchmark numbers into my changelog when I stop
hiding in RFC. ;)
Thanks,
Mathieu
(Add PPC maintainers in Cc)
Regards,
Boqun
quoted
Here are benchmarks of counter increment in various scenarios compared
to restartable sequences:
ARMv7 Processor rev 4 (v7l)
Machine model: Cubietruck
Counter increment speed (ns/increment)
1 thread 2 threads
global increment (baseline) 6 N/A
percpu rseq increment 50 52
percpu rseq spinlock 94 94
global atomic increment 48 74 (__sync_add_and_fetch_4)
global atomic CAS 50 172 (__sync_val_compare_and_swap_4)
global pthread mutex 148 862
ARMv7 Processor rev 10 (v7l)
Machine model: Wandboard
Counter increment speed (ns/increment)
1 thread 4 threads
global increment (baseline) 7 N/A
percpu rseq increment 50 50
percpu rseq spinlock 82 84
global atomic increment 44 262 (__sync_add_and_fetch_4)
global atomic CAS 46 316 (__sync_val_compare_and_swap_4)
global pthread mutex 146 1400
x86-64 Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz:
Counter increment speed (ns/increment)
1 thread 8 threads
global increment (baseline) 3.0 N/A
percpu rseq increment 3.6 3.8
percpu rseq spinlock 5.6 6.2
global LOCK; inc 8.0 166.4
global LOCK; cmpxchg 13.4 435.2
global pthread mutex 25.2 1363.6
* 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 migration 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
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.
----- On Jul 27, 2016, at 11:05 AM, Boqun Feng boqun.feng@gmail.com wrote:
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.
/* Re-enable the breakpoints for the signal stack */
thread_change_pc(current, regs);
+ rseq_signal_deliver(regs);
+
if (is32) {
if (ksig.ka.sa.sa_flags & SA_SIGINFO)
ret = handle_rt_signal32(&ksig, oldset, regs);
@@ -157,6 +159,7 @@ void do_notify_resume(struct pt_regs *regs, unsigned long
----- On Jul 27, 2016, at 11:05 AM, Boqun Feng boqun.feng-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org wrote:
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.
On Thu, Jul 28, 2016 at 02:59:45AM +0000, Mathieu Desnoyers wrote:
----- On Jul 27, 2016, at 11:05 AM, Boqun Feng boqun.feng-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org wrote:
quoted
As rseq syscall is enabled on PPC, implement the self-tests on PPC to
verify the implementation of the syscall.
Please note we only support 32bit userspace on BE kernel.
Signed-off-by: Boqun Feng <redacted>
---
tools/testing/selftests/rseq/param_test.c | 14 ++++
tools/testing/selftests/rseq/rseq.h | 120 ++++++++++++++++++++++++++++++
2 files changed, 134 insertions(+)
Can you check if defining has_fast_acquire_release() to 0 speeds up
performance significantly ? It turns the smp_lwsync() into a
compiler barrier() on the smp_load_acquire() side (fast-path), and
turn the smp_lwsync() into a membarrier system call instead of the
matching smp_store_release() (slow path).
Good point. Here are the numbers:
Power8 PSeries KVM Guest(64 VCPUs, the host has 16 cores, 128 hardware
threads):
Counter increment speed (ns/increment)
1 thread 2 threads 4 threads 8 threads 16 threads 32 threads
global increment (baseline) 6.5 N/A N/A N/A N/A N/A
percpu rseq increment 7.0 7.0 7.2 7.2 9.3 14.5
percpu rseq spinlock 18.5 18.5 18.6 18.8 25.5 52.7
So looks like defining has_fast_acquire_release() to 0 could benefit the
cases with more threads in current benchmark. I will send a updated
patch doing this.
And as discussed in IRC, I will also remove jump from rseq_finish()
fast-path in powerpc asm in the updated patch as you did for x86 and
ARM.
Regards,
Boqun
As rseq syscall is enabled on PPC, implement the self-tests on PPC to
verify the implementation of the syscall.
Please note we only support 32bit userspace on BE kernel.
Signed-off-by: Boqun Feng <redacted>
---
v1-->v2:
1. Remove branch in rseq_finish() fastpath
2. Use bne- instead of bne to jump when failure.
3. Use r17 instead of r16 for storing zero to rseq_cs, which
could save a register in rseq_finish() asm block.
tools/testing/selftests/rseq/param_test.c | 14 ++++
tools/testing/selftests/rseq/rseq.h | 112 ++++++++++++++++++++++++++++++
2 files changed, 126 insertions(+)
----- On Jul 28, 2016, at 12:43 AM, Boqun Feng boqun.feng-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org wrote:
On Thu, Jul 28, 2016 at 02:59:45AM +0000, Mathieu Desnoyers wrote:
quoted
----- On Jul 27, 2016, at 11:05 AM, Boqun Feng boqun.feng-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org wrote:
quoted
As rseq syscall is enabled on PPC, implement the self-tests on PPC to
verify the implementation of the syscall.
Please note we only support 32bit userspace on BE kernel.
Signed-off-by: Boqun Feng <redacted>
---
tools/testing/selftests/rseq/param_test.c | 14 ++++
tools/testing/selftests/rseq/rseq.h | 120 ++++++++++++++++++++++++++++++
2 files changed, 134 insertions(+)
Can you check if defining has_fast_acquire_release() to 0 speeds up
performance significantly ? It turns the smp_lwsync() into a
compiler barrier() on the smp_load_acquire() side (fast-path), and
turn the smp_lwsync() into a membarrier system call instead of the
matching smp_store_release() (slow path).
Good point. Here are the numbers:
Power8 PSeries KVM Guest(64 VCPUs, the host has 16 cores, 128 hardware
threads):
Counter increment speed (ns/increment)
1 thread 2 threads 4 threads 8 threads 16 threads 32 threads
global increment (baseline) 6.5 N/A N/A N/A
N/A N/A
percpu rseq increment 7.0 7.0 7.2 7.2
9.3 14.5
percpu rseq spinlock 18.5 18.5 18.6 18.8
25.5 52.7
So looks like defining has_fast_acquire_release() to 0 could benefit the
cases with more threads in current benchmark. I will send a updated
patch doing this.
Good to know the lwsync barrier overhead kicks in at that level of
workload on Power8.
And as discussed in IRC, I will also remove jump from rseq_finish()
fast-path in powerpc asm in the updated patch as you did for x86 and
ARM.
----- On Jul 28, 2016, at 3:37 AM, Boqun Feng boqun.feng-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org wrote:
As rseq syscall is enabled on PPC, implement the self-tests on PPC to
verify the implementation of the syscall.
Please note we only support 32bit userspace on BE kernel.
Picked into my rseq-fallback dev branch, thanks!
Mathieu
quoted hunk
Signed-off-by: Boqun Feng <redacted>
---
v1-->v2:
1. Remove branch in rseq_finish() fastpath
2. Use bne- instead of bne to jump when failure.
3. Use r17 instead of r16 for storing zero to rseq_cs, which
could save a register in rseq_finish() asm block.
tools/testing/selftests/rseq/param_test.c | 14 ++++
tools/testing/selftests/rseq/rseq.h | 112 ++++++++++++++++++++++++++++++
2 files changed, 126 insertions(+)
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-08-03 12:28:28
On Tue, Jul 26, 2016 at 03:02:19AM +0000, Mathieu Desnoyers wrote:
We really care about preemption here. Every migration implies a
preemption from a user-space perspective. If we would only care
about keeping the CPU id up-to-date, hooking into migration would be
enough. But since we want atomicity guarantees for restartable
sequences, we need to hook into preemption.
It allows user-space to perform update operations on per-cpu data without
requiring heavy-weight atomic operations.
Well, a CMPXCHG without LOCK prefix isn't all that expensive on x86.
It is however on PPC and possibly other architectures, so in name of
simplicity supporting only the one variant makes sense.
Do we either want to grow that alignment to L1_CACHE_BYTES or place a
comment near that it would be best for performance to ensure the whole
thing fits into 1 line?
Alternatively, growing the alignment to 4*8 would probably be sufficient
to ensure that and waste less bytes.
+struct rseq {
+ union {
+ struct {
+ /*
+ * Restartable sequences cpu_id field.
+ * Updated by the kernel, and read by user-space with
+ * single-copy atomicity semantics. Aligned on 32-bit.
+ * Negative values are reserved for user-space.
+ */
+ int32_t cpu_id;
+ /*
+ * Restartable sequences event_counter field.
+ * Updated by the kernel, and read by user-space with
+ * single-copy atomicity semantics. Aligned on 32-bit.
+ */
+ uint32_t event_counter;
+ } e;
+ /*
+ * On architectures with 64-bit aligned reads, both cpu_id and
+ * event_counter can be read with single-copy atomicity
+ * semantics.
+ */
+ uint64_t v;
+ } u;
+ /*
+ * Restartable sequences rseq_cs field.
+ * Updated by user-space, read by the kernel with
+ * single-copy atomicity semantics. Aligned on 64-bit.
+ */
+ RSEQ_FIELD_u32_u64(rseq_cs);
+} __attribute__((aligned(sizeof(uint64_t))));
2*sizeof(uint64_t) ?
Also, I think it would be good to have a comment explaining why this is
split in two structures? Don't you rely on the address dependency?
+/*
+ * Each restartable sequence assembly block defines a "struct rseq_cs"
+ * structure which describes the post_commit_ip address, and the
+ * abort_ip address where the kernel should move the thread instruction
+ * pointer if a rseq critical section assembly block is preempted or if
+ * a signal is delivered on top of a rseq critical section assembly
+ * block. It also contains a start_ip, which is the address of the start
+ * of the rseq assembly block, which is useful to debuggers.
+ *
+ * The algorithm for a restartable sequence assembly block is as
+ * follows:
+ *
+ * rseq_start()
+ *
+ * 0. Userspace loads the current event counter value from the
+ * event_counter field of the registered struct rseq TLS area,
+ *
+ * rseq_finish()
+ *
+ * Steps [1]-[3] (inclusive) need to be a sequence of instructions in
+ * userspace that can handle being moved to the abort_ip between any
+ * of those instructions.
+ *
+ * The abort_ip address needs to be equal or above the post_commit_ip.
Above, as in: abort_ip >= post_commit_ip? Would not 'after' or
greater-or-equal be easier to understand?
+ * Step [4] and the failure code step [F1] need to be at addresses
+ * equal or above the post_commit_ip.
idem.
+ * 1. Userspace stores the address of the struct rseq cs rseq
+ * assembly block descriptor into the rseq_cs field of the
+ * registered struct rseq TLS area.
And this should be something like up-store-release, which would
basically be a regular store, but such that the compiler is restrained
from placing the stores to the structure itself later.
+ *
+ * 2. Userspace tests to see whether the current event counter values
+ * match those loaded at [0]. Manually jumping to [F1] in case of
+ * a mismatch.
+ *
+ * Note that if we are preempted or interrupted by a signal
+ * after [1] and before post_commit_ip, then the kernel also
+ * performs the comparison performed in [2], and conditionally
+ * clears rseq_cs, then jumps us to abort_ip.
+ *
+ * 3. Userspace critical section final instruction before
+ * post_commit_ip is the commit. The critical section is
+ * self-terminating.
+ * [post_commit_ip]
+ *
+ * 4. Userspace clears the rseq_cs field of the struct rseq
+ * TLS area.
+ *
+ * 5. Return true.
+ *
+ * On failure at [2]:
+ *
+ * F1. Userspace clears the rseq_cs field of the struct rseq
+ * TLS area. Followed by step [F2].
+ *
+ * [abort_ip]
+ * F2. Return false.
+ */
+
+static int rseq_increment_event_counter(struct task_struct *t)
+{
+ if (__put_user(++t->rseq_event_counter,
+ &t->rseq->u.e.event_counter))
+ return -1;
+ return 0;
+}
Given we want all 3 of those values in a single line and doing 3
get_user() calls ends up doing 3 pairs of STAC/CLAC, should we not use
either copy_from_user_inatomic or unsafe_get_user() paired with
user_access_begin/end() pairs.
+ *abort_ip = (void __user *)ptr;
+ return 0;
+}
this and,
+static int rseq_ip_fixup(struct pt_regs *regs)
+{
+ struct task_struct *t = current;
+ void __user *post_commit_ip = NULL;
+ void __user *abort_ip = NULL;
+
+ if (rseq_get_rseq_cs(t, &post_commit_ip, &abort_ip))
+ return -1;
+
+ /* Handle potentially being within a critical section. */
+ if ((void __user *)instruction_pointer(regs) < post_commit_ip) {
Alternatively you can do:
if (likely(void __user *)instruction_pointer(regs) >= post_commit_ip)
return 0;
and you can safe an indent level below.
+ /*
+ * We need to clear rseq_cs upon entry into a signal
+ * handler nested on top of a rseq assembly block, so
+ * the signal handler will not be fixed up if itself
+ * interrupted by a nested signal handler or preempted.
+ */
+ if (clear_user(&t->rseq->rseq_cs,
+ sizeof(t->rseq->rseq_cs)))
+ return -1;
+
+ /*
+ * We set this after potentially failing in
+ * clear_user so that the signal arrives at the
+ * faulting rip.
+ */
+ instruction_pointer_set(regs, (unsigned long)abort_ip);
+ }
+ return 0;
+}
this function look like it should return bool.
+/*
+ * This resume handler should always be executed between any of:
+ * - preemption,
+ * - signal delivery,
+ * and return to user-space.
+ */
+void __rseq_handle_notify_resume(struct pt_regs *regs)
+{
+ struct task_struct *t = current;
+
+ if (unlikely(t->flags & PF_EXITING))
+ return;
+ if (!access_ok(VERIFY_WRITE, t->rseq, sizeof(*t->rseq)))
+ goto error;
+ if (__put_user(raw_smp_processor_id(), &t->rseq->u.e.cpu_id))
+ goto error;
+ if (rseq_increment_event_counter(t))
It seems a shame to not use a single __put_user() here. You did the
layout to explicitly allow for this, but then you don't.
+ if (!rseq) {
+ if (!current->rseq)
+ return -ENOENT;
+ return 0;
+ }
+
+ if (current->rseq) {
+ /*
+ * If rseq is already registered, check whether
+ * the provided address differs from the prior
+ * one.
+ */
+ if (current->rseq != rseq)
+ return -EBUSY;
Why explicitly allow resetting the same value?
+ } else {
+ /*
+ * If there was no rseq previously registered,
+ * we need to ensure the provided rseq is
+ * properly aligned and valid.
+ */
+ if (!IS_ALIGNED((unsigned long)rseq, sizeof(uint64_t)))
+ return -EINVAL;
+ if (!access_ok(VERIFY_WRITE, rseq, sizeof(*rseq)))
+ return -EFAULT;
GCC has __alignof__(struct rseq) for this. And as per the above, I would
recommend you change this to 2*sizeof(u64) to ensure the whole thing
fits in a single line.
quoted hunk
+ current->rseq = rseq;
+ /*
+ * If rseq was previously inactive, and has just
+ * been registered, ensure the cpu_id and
+ * event_counter fields are updated before
+ * returning to user-space.
+ */
+ rseq_set_notify_resume(current);
+ }
+
+ return 0;
+}
One thing I considered is doing something like:
static inline void rseq_sched_out(struct task_struct *t)
{
unsigned long ptr;
int err;
if (!t->rseq)
return;
err = __get_user(ptr, &t->rseq->rseq_cs);
if (err || ptr)
set_tsk_thread_flag(t, TIF_NOTIFY_RESUME);
}
That will optimistically try to read the rseq_cs pointer and, on success
and empty (the most likely case) avoid setting the TIF flag.
This will require an explicit migration hook to unconditionally set the
TIF flag such that we keep the cpu_id field correct of course.
And obviously we can do this later, as an optimization. Its just
something I figured might be worth it.
Do we either want to grow that alignment to L1_CACHE_BYTES or place a
comment near that it would be best for performance to ensure the whole
thing fits into 1 line?
Alternatively, growing the alignment to 4*8 would probably be sufficient
to ensure that and waste less bytes.
quoted
+struct rseq {
+ union {
+ struct {
+ /*
+ * Restartable sequences cpu_id field.
+ * Updated by the kernel, and read by user-space with
+ * single-copy atomicity semantics. Aligned on 32-bit.
+ * Negative values are reserved for user-space.
+ */
+ int32_t cpu_id;
+ /*
+ * Restartable sequences event_counter field.
+ * Updated by the kernel, and read by user-space with
+ * single-copy atomicity semantics. Aligned on 32-bit.
+ */
+ uint32_t event_counter;
+ } e;
+ /*
+ * On architectures with 64-bit aligned reads, both cpu_id and
+ * event_counter can be read with single-copy atomicity
+ * semantics.
+ */
+ uint64_t v;
+ } u;
+ /*
+ * Restartable sequences rseq_cs field.
+ * Updated by user-space, read by the kernel with
+ * single-copy atomicity semantics. Aligned on 64-bit.
+ */
+ RSEQ_FIELD_u32_u64(rseq_cs);
+} __attribute__((aligned(sizeof(uint64_t))));
2*sizeof(uint64_t) ?
Also, I think it would be good to have a comment explaining why this is
split in two structures? Don't you rely on the address dependency?
+/*
+ * Each restartable sequence assembly block defines a "struct rseq_cs"
+ * structure which describes the post_commit_ip address, and the
+ * abort_ip address where the kernel should move the thread instruction
+ * pointer if a rseq critical section assembly block is preempted or if
+ * a signal is delivered on top of a rseq critical section assembly
+ * block. It also contains a start_ip, which is the address of the start
+ * of the rseq assembly block, which is useful to debuggers.
+ *
+ * The algorithm for a restartable sequence assembly block is as
+ * follows:
+ *
+ * rseq_start()
+ *
+ * 0. Userspace loads the current event counter value from the
+ * event_counter field of the registered struct rseq TLS area,
+ *
+ * rseq_finish()
+ *
+ * Steps [1]-[3] (inclusive) need to be a sequence of instructions in
+ * userspace that can handle being moved to the abort_ip between any
+ * of those instructions.
+ *
+ * The abort_ip address needs to be equal or above the post_commit_ip.
Above, as in: abort_ip >= post_commit_ip? Would not 'after' or
greater-or-equal be easier to understand?
quoted
+ * Step [4] and the failure code step [F1] need to be at addresses
+ * equal or above the post_commit_ip.
idem.
quoted
+ * 1. Userspace stores the address of the struct rseq cs rseq
+ * assembly block descriptor into the rseq_cs field of the
+ * registered struct rseq TLS area.
And this should be something like up-store-release, which would
basically be a regular store, but such that the compiler is restrained
from placing the stores to the structure itself later.
quoted
+ *
+ * 2. Userspace tests to see whether the current event counter values
+ * match those loaded at [0]. Manually jumping to [F1] in case of
+ * a mismatch.
+ *
+ * Note that if we are preempted or interrupted by a signal
+ * after [1] and before post_commit_ip, then the kernel also
+ * performs the comparison performed in [2], and conditionally
+ * clears rseq_cs, then jumps us to abort_ip.
+ *
+ * 3. Userspace critical section final instruction before
+ * post_commit_ip is the commit. The critical section is
+ * self-terminating.
+ * [post_commit_ip]
+ *
+ * 4. Userspace clears the rseq_cs field of the struct rseq
+ * TLS area.
+ *
+ * 5. Return true.
+ *
+ * On failure at [2]:
+ *
+ * F1. Userspace clears the rseq_cs field of the struct rseq
+ * TLS area. Followed by step [F2].
+ *
+ * [abort_ip]
+ * F2. Return false.
+ */
+
+static int rseq_increment_event_counter(struct task_struct *t)
+{
+ if (__put_user(++t->rseq_event_counter,
+ &t->rseq->u.e.event_counter))
+ return -1;
+ return 0;
+}
Given we want all 3 of those values in a single line and doing 3
get_user() calls ends up doing 3 pairs of STAC/CLAC, should we not use
either copy_from_user_inatomic or unsafe_get_user() paired with
user_access_begin/end() pairs.
quoted
+ *abort_ip = (void __user *)ptr;
+ return 0;
+}
this and,
quoted
+static int rseq_ip_fixup(struct pt_regs *regs)
+{
+ struct task_struct *t = current;
+ void __user *post_commit_ip = NULL;
+ void __user *abort_ip = NULL;
+
+ if (rseq_get_rseq_cs(t, &post_commit_ip, &abort_ip))
+ return -1;
+
+ /* Handle potentially being within a critical section. */
+ if ((void __user *)instruction_pointer(regs) < post_commit_ip) {
Alternatively you can do:
if (likely(void __user *)instruction_pointer(regs) >= post_commit_ip)
return 0;
and you can safe an indent level below.
quoted
+ /*
+ * We need to clear rseq_cs upon entry into a signal
+ * handler nested on top of a rseq assembly block, so
+ * the signal handler will not be fixed up if itself
+ * interrupted by a nested signal handler or preempted.
+ */
+ if (clear_user(&t->rseq->rseq_cs,
+ sizeof(t->rseq->rseq_cs)))
+ return -1;
+
+ /*
+ * We set this after potentially failing in
+ * clear_user so that the signal arrives at the
+ * faulting rip.
+ */
+ instruction_pointer_set(regs, (unsigned long)abort_ip);
+ }
+ return 0;
+}
this function look like it should return bool.
quoted
+/*
+ * This resume handler should always be executed between any of:
+ * - preemption,
+ * - signal delivery,
+ * and return to user-space.
+ */
+void __rseq_handle_notify_resume(struct pt_regs *regs)
+{
+ struct task_struct *t = current;
+
+ if (unlikely(t->flags & PF_EXITING))
+ return;
+ if (!access_ok(VERIFY_WRITE, t->rseq, sizeof(*t->rseq)))
+ goto error;
+ if (__put_user(raw_smp_processor_id(), &t->rseq->u.e.cpu_id))
+ goto error;
+ if (rseq_increment_event_counter(t))
It seems a shame to not use a single __put_user() here. You did the
layout to explicitly allow for this, but then you don't.
+ if (!rseq) {
+ if (!current->rseq)
+ return -ENOENT;
+ return 0;
+ }
+
+ if (current->rseq) {
+ /*
+ * If rseq is already registered, check whether
+ * the provided address differs from the prior
+ * one.
+ */
+ if (current->rseq != rseq)
+ return -EBUSY;
Why explicitly allow resetting the same value?
quoted
+ } else {
+ /*
+ * If there was no rseq previously registered,
+ * we need to ensure the provided rseq is
+ * properly aligned and valid.
+ */
+ if (!IS_ALIGNED((unsigned long)rseq, sizeof(uint64_t)))
+ return -EINVAL;
+ if (!access_ok(VERIFY_WRITE, rseq, sizeof(*rseq)))
+ return -EFAULT;
GCC has __alignof__(struct rseq) for this. And as per the above, I would
recommend you change this to 2*sizeof(u64) to ensure the whole thing
fits in a single line.
quoted
+ current->rseq = rseq;
+ /*
+ * If rseq was previously inactive, and has just
+ * been registered, ensure the cpu_id and
+ * event_counter fields are updated before
+ * returning to user-space.
+ */
+ rseq_set_notify_resume(current);
+ }
+
+ return 0;
+}
One thing I considered is doing something like:
static inline void rseq_sched_out(struct task_struct *t)
{
unsigned long ptr;
int err;
if (!t->rseq)
return;
err = __get_user(ptr, &t->rseq->rseq_cs);
if (err || ptr)
set_tsk_thread_flag(t, TIF_NOTIFY_RESUME);
}
That will optimistically try to read the rseq_cs pointer and, on success
and empty (the most likely case) avoid setting the TIF flag.
This will require an explicit migration hook to unconditionally set the
TIF flag such that we keep the cpu_id field correct of course.
And obviously we can do this later, as an optimization. Its just
something I figured might be worth it.
It would be good to have multiple people here, if we lack volunteers I'd
be willing. Paul, Andrew any of you guys willing?
I volunteer to review related patches, do tests/benchmarks(esp. on PPC)
and try to fix/improve any issue as I can.
Mathieu, may I join the party? ;-)
Regards,
Boqun
quoted
+L: linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
+S: Supported
+F: kernel/rseq.c
+F: include/uapi/linux/rseq.h
+
GFS2 FILE SYSTEM
M: Steven Whitehouse [off-list ref]
M: Bob Peterson [off-list ref]
From: Andy Lutomirski <luto@amacapital.net> Date: 2016-08-03 16:43:59
On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra [off-list ref] wrote:
On Tue, Jul 26, 2016 at 03:02:19AM +0000, Mathieu Desnoyers wrote:
quoted
We really care about preemption here. Every migration implies a
preemption from a user-space perspective. If we would only care
about keeping the CPU id up-to-date, hooking into migration would be
enough. But since we want atomicity guarantees for restartable
sequences, we need to hook into preemption.
quoted
It allows user-space to perform update operations on per-cpu data without
requiring heavy-weight atomic operations.
Well, a CMPXCHG without LOCK prefix isn't all that expensive on x86.
It is however on PPC and possibly other architectures, so in name of
simplicity supporting only the one variant makes sense.
I wouldn't want to depend on CMPXCHG. But imagine we had primitives
that were narrower than the full abort-on-preemption primitive.
Specifically, suppose we had abort if (actual cpu != expected_cpu ||
*aptr != aval). We could do things like:
expected_cpu = cpu;
aval = NULL; // disarm for now
begin();
aval = event_count[cpu] + 1;
event_count[cpu] = aval;
event_count[cpu]++;
... compute something ...
// arm the rest of it
aptr = &event_count[cpu];
if (*aptr != aval)
goto fail;
*thing_im_writing = value_i_computed;
end();
The idea here is that we don't rely on the scheduler to increment the
event count at all, which means that we get to determine the scope of
what kinds of access conflicts we care about ourselves.
This has an obvious downside: it's more complicated.
It has several benefits, I think. It's debuggable without hassle
(unless someone, accidentally or otherwise, sets aval incorrectly).
It also allows much longer critical sections to work well, as merely
being preempted in the middle won't cause an abort any more.
So I'm hoping to understand whether we could make something like this
work. This whole thing is roughly equivalent to abort-if-migrated
plus an atomic "if (*aptr == aval) *b = c;" operation.
(I think that, if this worked, we could improve it a bit by making the
abort operation jump back to the "if (*aptr != aval) goto fail;" code,
which should reduce the scope for error a bit and also reduces the
need for extra code paths that only execute on an abort.)
From: Christoph Lameter <hidden> Date: 2016-08-03 18:30:38
On Tue, 26 Jul 2016, Mathieu Desnoyers wrote:
quoted
What problem does this solve?
It allows user-space to perform update operations on per-cpu data without
requiring heavy-weight atomic operations.
This is great but seems to indicate that such a facility would be better
for kernel code instread of user space code.
First, prohibiting migration from user-space has been frowned upon
by scheduler developers for a long time, and I doubt this mindset will
change.
Note that the task isolation patchset from Chris Metcalf does something
that goes a long way towards this. If you set strict isolation mode then
the kernel will terminate the process or notify you if the scheduler
becomes involved. In some way we are getting that as a side effect.
Also prohibiting migration is trivial form user space. Just do a taskset
to a single cpu.
From: Christoph Lameter <hidden> Date: 2016-08-03 18:31:35
On Wed, 3 Aug 2016, Andy Lutomirski wrote:
quoted
Well, a CMPXCHG without LOCK prefix isn't all that expensive on x86.
It is however on PPC and possibly other architectures, so in name of
simplicity supporting only the one variant makes sense.
I wouldn't want to depend on CMPXCHG. But imagine we had primitives
that were narrower than the full abort-on-preemption primitive.
Specifically, suppose we had abort if (actual cpu != expected_cpu ||
*aptr != aval). We could do things like:
The latency issues that are addressed by restartable sequences require
minimim instruction overhead. Lockless CMPXCHG is very important in that
area and I would not simply remove it from consideration.
On Wed, Aug 03, 2016 at 09:37:57AM -0700, Andy Lutomirski wrote:
On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra [off-list ref] wrote:
quoted
On Tue, Jul 26, 2016 at 03:02:19AM +0000, Mathieu Desnoyers wrote:
quoted
We really care about preemption here. Every migration implies a
preemption from a user-space perspective. If we would only care
about keeping the CPU id up-to-date, hooking into migration would be
enough. But since we want atomicity guarantees for restartable
sequences, we need to hook into preemption.
quoted
It allows user-space to perform update operations on per-cpu data without
requiring heavy-weight atomic operations.
Well, a CMPXCHG without LOCK prefix isn't all that expensive on x86.
It is however on PPC and possibly other architectures, so in name of
simplicity supporting only the one variant makes sense.
I wouldn't want to depend on CMPXCHG. But imagine we had primitives
that were narrower than the full abort-on-preemption primitive.
Specifically, suppose we had abort if (actual cpu != expected_cpu ||
*aptr != aval). We could do things like:
expected_cpu = cpu;
aval = NULL; // disarm for now
begin();
aval = event_count[cpu] + 1;
event_count[cpu] = aval;
event_count[cpu]++;
This line is redundant, right? Because it will guarantee a failure even
in no-contention cases.
... compute something ...
// arm the rest of it
aptr = &event_count[cpu];
if (*aptr != aval)
goto fail;
*thing_im_writing = value_i_computed;
end();
The idea here is that we don't rely on the scheduler to increment the
event count at all, which means that we get to determine the scope of
what kinds of access conflicts we care about ourselves.
If we increase the event count in userspace, how could we prevent two
userspace threads from racing on the event_count[cpu] field? For
example:
CPU 0
================
{event_count[0] is initially 0}
[Thread 1]
begin();
aval = event_count[cpu] + 1; // 1
(preempted)
[Thread 2]
begin();
aval = event_count[cpu] + 1; // 1, too
event_count[cpu] = aval; // event_count[0] is 1
(preempted)
[Thread 1]
event_count[cpu] = aval; // event_count[0] is 1
...
aptr = &event_count[cpu];
if (*aptr != aval) // false.
...
[Thread 2]
aptr = &event_count[cpu];
if (*aptr != aval) // false.
...
, in which case, both the critical sections are successful, and Thread 1
and Thread 2 will race on *thing_im_writing.
Am I missing your point here?
Regards,
Boqun
This has an obvious downside: it's more complicated.
It has several benefits, I think. It's debuggable without hassle
(unless someone, accidentally or otherwise, sets aval incorrectly).
It also allows much longer critical sections to work well, as merely
being preempted in the middle won't cause an abort any more.
So I'm hoping to understand whether we could make something like this
work. This whole thing is roughly equivalent to abort-if-migrated
plus an atomic "if (*aptr == aval) *b = c;" operation.
(I think that, if this worked, we could improve it a bit by making the
abort operation jump back to the "if (*aptr != aval) goto fail;" code,
which should reduce the scope for error a bit and also reduces the
need for extra code paths that only execute on an abort.)
From: Andy Lutomirski <luto@amacapital.net> Date: 2016-08-04 05:01:44
On Aug 3, 2016 11:31 AM, "Christoph Lameter" [off-list ref] wrote:
On Wed, 3 Aug 2016, Andy Lutomirski wrote:
quoted
quoted
Well, a CMPXCHG without LOCK prefix isn't all that expensive on x86.
It is however on PPC and possibly other architectures, so in name of
simplicity supporting only the one variant makes sense.
I wouldn't want to depend on CMPXCHG. But imagine we had primitives
that were narrower than the full abort-on-preemption primitive.
Specifically, suppose we had abort if (actual cpu != expected_cpu ||
*aptr != aval). We could do things like:
The latency issues that are addressed by restartable sequences require
minimim instruction overhead. Lockless CMPXCHG is very important in that
area and I would not simply remove it from consideration.
What I mean is: I think the solution shouldn't depend on the
x86-specific unlocked CMPXCHG instruction if it can be avoided.
From: Andy Lutomirski <luto@amacapital.net> Date: 2016-08-04 05:11:22
On Wed, Aug 3, 2016 at 9:27 PM, Boqun Feng [off-list ref] wrote:
On Wed, Aug 03, 2016 at 09:37:57AM -0700, Andy Lutomirski wrote:
quoted
On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra [off-list ref] wrote:
quoted
On Tue, Jul 26, 2016 at 03:02:19AM +0000, Mathieu Desnoyers wrote:
quoted
We really care about preemption here. Every migration implies a
preemption from a user-space perspective. If we would only care
about keeping the CPU id up-to-date, hooking into migration would be
enough. But since we want atomicity guarantees for restartable
sequences, we need to hook into preemption.
quoted
It allows user-space to perform update operations on per-cpu data without
requiring heavy-weight atomic operations.
Well, a CMPXCHG without LOCK prefix isn't all that expensive on x86.
It is however on PPC and possibly other architectures, so in name of
simplicity supporting only the one variant makes sense.
I wouldn't want to depend on CMPXCHG. But imagine we had primitives
that were narrower than the full abort-on-preemption primitive.
Specifically, suppose we had abort if (actual cpu != expected_cpu ||
*aptr != aval). We could do things like:
expected_cpu = cpu;
aval = NULL; // disarm for now
begin();
aval = event_count[cpu] + 1;
event_count[cpu] = aval;
event_count[cpu]++;
This line is redundant, right? Because it will guarantee a failure even
in no-contention cases.
quoted
... compute something ...
// arm the rest of it
aptr = &event_count[cpu];
if (*aptr != aval)
goto fail;
*thing_im_writing = value_i_computed;
end();
The idea here is that we don't rely on the scheduler to increment the
event count at all, which means that we get to determine the scope of
what kinds of access conflicts we care about ourselves.
If we increase the event count in userspace, how could we prevent two
userspace threads from racing on the event_count[cpu] field? For
example:
CPU 0
================
{event_count[0] is initially 0}
[Thread 1]
begin();
aval = event_count[cpu] + 1; // 1
(preempted)
[Thread 2]
begin();
aval = event_count[cpu] + 1; // 1, too
event_count[cpu] = aval; // event_count[0] is 1
You're right :( This would work with an xadd instruction, but that's
very slow and doesn't exist on most architectures. It could also work
if we did:
aval = some_tls_value++;
where some_tls_value is set up such that no two threads could ever end
up with the same values (using high bits as thread ids, perhaps), but
that's messy. Maybe my idea is no good.
It would be good to have multiple people here, if we lack volunteers I'd
be willing. Paul, Andrew any of you guys willing?
I volunteer to review related patches, do tests/benchmarks(esp. on PPC)
and try to fix/improve any issue as I can.
Mathieu, may I join the party? ;-)
Hi!
I'm glad to see so much interest in helping me maintain rseq :)
I'll therefore tentatively add the following lines to the maintainers
list in my next round:
RESTARTABLE SEQUENCES SUPPORT
M: Mathieu Desnoyers [off-list ref]
M: Peter Zijlstra [off-list ref]
M: "Paul E. McKenney" [off-list ref]
M: Boqun Feng [off-list ref]
L: linux-kernel@vger.kernel.org
S: Supported
F: kernel/rseq.c
F: include/uapi/linux/rseq.h
Thanks!
Mathieu
Regards,
Boqun
quoted
quoted
+L: linux-kernel@vger.kernel.org
+S: Supported
+F: kernel/rseq.c
+F: include/uapi/linux/rseq.h
+
GFS2 FILE SYSTEM
M: Steven Whitehouse [off-list ref]
M: Bob Peterson [off-list ref]
It would be good to have multiple people here, if we lack volunteers I'd
be willing. Paul, Andrew any of you guys willing?
I volunteer to review related patches, do tests/benchmarks(esp. on PPC)
and try to fix/improve any issue as I can.
Mathieu, may I join the party? ;-)
Hi!
I'm glad to see so much interest in helping me maintain rseq :)
I'll therefore tentatively add the following lines to the maintainers
list in my next round:
RESTARTABLE SEQUENCES SUPPORT
M: Mathieu Desnoyers [off-list ref]
M: Peter Zijlstra [off-list ref]
M: "Paul E. McKenney" [off-list ref]
M: Boqun Feng [off-list ref]
L: linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
S: Supported
F: kernel/rseq.c
F: include/uapi/linux/rseq.h
Thank you, Mathieu ;-)
Maybe we also should put the selftest directory here? Like:
F: tools/testing/selftests/rseq
Of course, this line better be added in patch 7 rather than patch 1.
Regards,
Boqun
Thanks!
Mathieu
quoted
Regards,
Boqun
quoted
quoted
+L: linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
+S: Supported
+F: kernel/rseq.c
+F: include/uapi/linux/rseq.h
+
GFS2 FILE SYSTEM
M: Steven Whitehouse [off-list ref]
M: Bob Peterson [off-list ref]
It would be good to have multiple people here, if we lack volunteers I'd
be willing. Paul, Andrew any of you guys willing?
I volunteer to review related patches, do tests/benchmarks(esp. on PPC)
and try to fix/improve any issue as I can.
Mathieu, may I join the party? ;-)
Hi!
I'm glad to see so much interest in helping me maintain rseq :)
I'll therefore tentatively add the following lines to the maintainers
list in my next round:
RESTARTABLE SEQUENCES SUPPORT
M: Mathieu Desnoyers [off-list ref]
M: Peter Zijlstra [off-list ref]
M: "Paul E. McKenney" [off-list ref]
M: Boqun Feng [off-list ref]
L: linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
S: Supported
F: kernel/rseq.c
F: include/uapi/linux/rseq.h
Thank you, Mathieu ;-)
Maybe we also should put the selftest directory here? Like:
F: tools/testing/selftests/rseq
Of course, this line better be added in patch 7 rather than patch 1.
Adding this to patch 7, with a "/" at the end of the line, since it
targets an entire directory.
Thanks,
Mathieu
Regards,
Boqun
quoted
Thanks!
Mathieu
quoted
Regards,
Boqun
quoted
quoted
+L: linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
+S: Supported
+F: kernel/rseq.c
+F: include/uapi/linux/rseq.h
+
GFS2 FILE SYSTEM
M: Steven Whitehouse [off-list ref]
M: Bob Peterson [off-list ref]
On Wed, Aug 03, 2016 at 10:03:32PM -0700, Andy Lutomirski wrote:
On Wed, Aug 3, 2016 at 9:27 PM, Boqun Feng [off-list ref] wrote:
quoted
On Wed, Aug 03, 2016 at 09:37:57AM -0700, Andy Lutomirski wrote:
quoted
On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra [off-list ref] wrote:
quoted
On Tue, Jul 26, 2016 at 03:02:19AM +0000, Mathieu Desnoyers wrote:
quoted
We really care about preemption here. Every migration implies a
preemption from a user-space perspective. If we would only care
about keeping the CPU id up-to-date, hooking into migration would be
enough. But since we want atomicity guarantees for restartable
sequences, we need to hook into preemption.
quoted
It allows user-space to perform update operations on per-cpu data without
requiring heavy-weight atomic operations.
Well, a CMPXCHG without LOCK prefix isn't all that expensive on x86.
It is however on PPC and possibly other architectures, so in name of
simplicity supporting only the one variant makes sense.
I wouldn't want to depend on CMPXCHG. But imagine we had primitives
that were narrower than the full abort-on-preemption primitive.
Specifically, suppose we had abort if (actual cpu != expected_cpu ||
*aptr != aval). We could do things like:
expected_cpu = cpu;
aval = NULL; // disarm for now
begin();
aval = event_count[cpu] + 1;
event_count[cpu] = aval;
event_count[cpu]++;
This line is redundant, right? Because it will guarantee a failure even
in no-contention cases.
quoted
... compute something ...
// arm the rest of it
aptr = &event_count[cpu];
if (*aptr != aval)
goto fail;
*thing_im_writing = value_i_computed;
end();
The idea here is that we don't rely on the scheduler to increment the
event count at all, which means that we get to determine the scope of
what kinds of access conflicts we care about ourselves.
If we increase the event count in userspace, how could we prevent two
userspace threads from racing on the event_count[cpu] field? For
example:
CPU 0
================
{event_count[0] is initially 0}
[Thread 1]
begin();
aval = event_count[cpu] + 1; // 1
(preempted)
[Thread 2]
begin();
aval = event_count[cpu] + 1; // 1, too
event_count[cpu] = aval; // event_count[0] is 1
You're right :( This would work with an xadd instruction, but that's
very slow and doesn't exist on most architectures. It could also work
if we did:
aval = some_tls_value++;
where some_tls_value is set up such that no two threads could ever end
up with the same values (using high bits as thread ids, perhaps), but
that's messy. Maybe my idea is no good.
This is a little more complex, plus I failed to find a way to do an
atomic "if (*aptr == aval) *b = c" in userspace ;-(
However, I'm thinking maybe we can use some tricks to avoid unnecessary
aborts-on-preemption.
First of all, I notice we haven't make any constraint on what kind of
memory objects could be "protected" by rseq critical sections yet. And I
think this is something we should decide before adding this feature into
kernel.
We can do some optimization if we have some constraints. For example, if
the memory objects inside the rseq critical sections could only be
modified by userspace programs, we therefore don't need to abort
immediately when userspace task -> kernel task context switch.
Further more, if the memory objects inside the rseq critical sections
could only be modified by userspace programs that have registered their
rseq structures, we don't need to abort immediately between the context
switches between two rseq-unregistered tasks or one rseq-registered
task and one rseq-unregistered task.
Instead, we do tricks as follow:
defining a percpu pointer in kernel:
DEFINE_PER_CPU(struct task_struct *, rseq_owner);
and a cpu field in struct task_struct:
struct task_struct {
...
#ifdef CONFIG_RSEQ
struct rseq __user *rseq;
uint32_t rseq_event_counter;
int rseq_cpu;
#endif
...
};
(task_struct::rseq_cpu should be initialized as -1.)
each time at sched out(in rseq_sched_out()), we do something like:
if (prev->rseq) {
raw_cpu_write(rseq_owner, prev);
prev->rseq_cpu = smp_processor_id();
}
each time sched in(in rseq_handle_notify_resume()), we do something
like:
if (current->rseq &&
(this_cpu_read(rseq_owner) != current ||
current->rseq_cpu != smp_processor_id()))
__rseq_handle_notify_resume(regs);
(Also need to modify rseq_signal_deliver() to call
__rseq_handle_notify_resume() directly).
I think this could save some unnecessary aborts-on-preemption, however,
TBH, I'm too sleepy to verify every corner case. Will recheck this
tomorrow.
Regards,
Boqun
This is kernel code, should we not use u32 instead?
Good point. Will fix.
Also, do we want a comment somewhere that explains why overflow isn't a
problem?
I can add a comment about rseq_increment_event_counter stating:
* Overflow of the event counter is not a problem in practice. It
* increments at most once between each user-space thread instruction
* executed, so we would need a thread to execute 2^32 instructions or
* more between rseq_start() and rseq_finish(), while single-stepping,
* for this to be an issue.
Is it fine, or should we be more conservative and care about the overflow,
extending the counter to a 64-bit value in the process ?
quoted
+#endif
/* CPU-specific state of this task */
struct thread_struct thread;
/*
Maybe I missed it, but why do we want to hook into NOTIFY_RESUME and not
have our own TIF flag?
The short answer is that used the same approach as Paul Turner's patchset. ;)
Through a deeper look into this, the only times we set the flag is when
preempting and delivering a signal to a thread that has registered to
rseq.
Upon return to user-space with the flag set, the performance difference
between having our own flag and hopping into the NOTIFY_RESUME bandwagon
is that we can skip the various tests in exit_to_usermode_loop()
with our own flag, at the expense of crowding the thread flags even
nearer to filling up 32 bits, which will at some point require extra
tests on the fast-path.
Thinking about it, one benchmark I have not done so far is to modify
hackbench so it registers its threads with the rseq system call. We
can then figure out whether reserving a flag for rseq is justified or
not.
Comparing 10 runs of hackbench registering its sender/receiver threads
with unmodified hackbench: (hackbench -l 100000)
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.7 defconfig+localyesconfig,
restartable sequences series applied.
Avg. Time (s) Std.dev. (s)
Unmodified Hackbench 40.5 0.1
Rseq-Registered Hackbench Threads 40.4 0.1
So initial results seems to indicate that adding the notify_resume
handling upon preemption does not have noticeable effects on
performance, so I don't consider it worthwhile to try optimizing
it by reserving its own thread flag. Or perhaps am I missing something
important here ?
deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE
+ * SOFTWARE.
+ */
+
+#ifdef __KERNEL__
+# include <linux/types.h>
+#else /* #ifdef __KERNEL__ */
+# include <stdint.h>
+#endif /* #else #ifdef __KERNEL__ */
+
+#include <asm/byteorder.h>
+
+#ifdef __LP64__
+# define RSEQ_FIELD_u32_u64(field) uint64_t field
+#elif defined(__BYTE_ORDER) ? \
+ __BYTE_ORDER == __BIG_ENDIAN : defined(__BIG_ENDIAN)
+# define RSEQ_FIELD_u32_u64(field) uint32_t _padding ## field, field
+#else
+# define RSEQ_FIELD_u32_u64(field) uint32_t field, _padding ## field
+#endif
+
+struct rseq_cs {
+ RSEQ_FIELD_u32_u64(start_ip);
+ RSEQ_FIELD_u32_u64(post_commit_ip);
+ RSEQ_FIELD_u32_u64(abort_ip);
+} __attribute__((aligned(sizeof(uint64_t))));
Do we either want to grow that alignment to L1_CACHE_BYTES or place a
comment near that it would be best for performance to ensure the whole
thing fits into 1 line?
Alternatively, growing the alignment to 4*8 would probably be sufficient
to ensure that and waste less bytes.
I am tempted to go for an alignment of 4 * sizeof(uint64_t) to ensure it
is contained within a single cache-line without wasting space uselessly,
adding the following comment:
/*
* struct rseq_cs is aligned on 4 * 8 bytes to ensure it is always
* contained within a single cache-line.
*/
There seems to be no gain in aligning it on a larger value, because it
is only ever read at run-time (never updated), so there can be no
false-sharing.
I'm updating the selftests rseq.h accordingly.
quoted
+struct rseq {
+ union {
+ struct {
+ /*
+ * Restartable sequences cpu_id field.
+ * Updated by the kernel, and read by user-space with
+ * single-copy atomicity semantics. Aligned on 32-bit.
+ * Negative values are reserved for user-space.
+ */
+ int32_t cpu_id;
+ /*
+ * Restartable sequences event_counter field.
+ * Updated by the kernel, and read by user-space with
+ * single-copy atomicity semantics. Aligned on 32-bit.
+ */
+ uint32_t event_counter;
+ } e;
+ /*
+ * On architectures with 64-bit aligned reads, both cpu_id and
+ * event_counter can be read with single-copy atomicity
+ * semantics.
+ */
+ uint64_t v;
+ } u;
+ /*
+ * Restartable sequences rseq_cs field.
+ * Updated by user-space, read by the kernel with
+ * single-copy atomicity semantics. Aligned on 64-bit.
+ */
+ RSEQ_FIELD_u32_u64(rseq_cs);
+} __attribute__((aligned(sizeof(uint64_t))));
2*sizeof(uint64_t) ?
Yes. Will do.
Also, I think it would be good to have a comment explaining why this is
split in two structures? Don't you rely on the address dependency?
The comment above the rseq_cs fields needs clarification, how about:
/*
* Restartable sequences rseq_cs field.
* Contains NULL when no critical section is active for the
* current thread, or holds a pointer to the currently active
* struct rseq_cs.
* Updated by user-space at the beginning and end of assembly
* instruction sequence block, and by the kernel when it
* restarts an assembly instruction sequence block. Read by the
* kernel with single-copy atomicity semantics. Aligned on
* 64-bit.
*/
This really explains that rseq_cs field of struct rseq holds a pointer
to the current struct rseq_cs (or NULL), which makes it obvious why this
needs to be two different structures.
+/*
+ * Each restartable sequence assembly block defines a "struct rseq_cs"
+ * structure which describes the post_commit_ip address, and the
+ * abort_ip address where the kernel should move the thread instruction
+ * pointer if a rseq critical section assembly block is preempted or if
+ * a signal is delivered on top of a rseq critical section assembly
+ * block. It also contains a start_ip, which is the address of the start
+ * of the rseq assembly block, which is useful to debuggers.
+ *
+ * The algorithm for a restartable sequence assembly block is as
+ * follows:
+ *
+ * rseq_start()
+ *
+ * 0. Userspace loads the current event counter value from the
+ * event_counter field of the registered struct rseq TLS area,
+ *
+ * rseq_finish()
+ *
+ * Steps [1]-[3] (inclusive) need to be a sequence of instructions in
+ * userspace that can handle being moved to the abort_ip between any
+ * of those instructions.
+ *
+ * The abort_ip address needs to be equal or above the post_commit_ip.
Above, as in: abort_ip >= post_commit_ip? Would not 'after' or
greater-or-equal be easier to understand?
Fixed. Using "lesser" and "greater-or-equal" for consistency.
quoted
+ * Step [4] and the failure code step [F1] need to be at addresses
+ * equal or above the post_commit_ip.
idem.
Fixed.
Combined with other recent feedback, this becomes:
* The abort_ip address needs to be lesser than start_ip, or
* greater-or-equal the post_commit_ip. Step [4] and the failure
* code step [F1] need to be at addresses lesser than start_ip, or
* greater-or-equal the post_commit_ip.
quoted
+ * 1. Userspace stores the address of the struct rseq cs rseq
+ * assembly block descriptor into the rseq_cs field of the
+ * registered struct rseq TLS area.
And this should be something like up-store-release, which would
basically be a regular store, but such that the compiler is restrained
from placing the stores to the structure itself later.
The compiler should also prevents following loads to be moved before this
store. Updated to:
* 1. Userspace stores the address of the struct rseq_cs assembly
* block descriptor into the rseq_cs field of the registered
* struct rseq TLS area. This update is performed through a single
* store, followed by a compiler barrier which prevents the
* compiler from moving following loads or stores before this
* store.
quoted
+ *
+ * 2. Userspace tests to see whether the current event counter values
+ * match those loaded at [0]. Manually jumping to [F1] in case of
+ * a mismatch.
+ *
+ * Note that if we are preempted or interrupted by a signal
+ * after [1] and before post_commit_ip, then the kernel also
+ * performs the comparison performed in [2], and conditionally
+ * clears rseq_cs, then jumps us to abort_ip.
+ *
+ * 3. Userspace critical section final instruction before
+ * post_commit_ip is the commit. The critical section is
+ * self-terminating.
+ * [post_commit_ip]
+ *
+ * 4. Userspace clears the rseq_cs field of the struct rseq
+ * TLS area.
+ *
+ * 5. Return true.
+ *
+ * On failure at [2]:
+ *
+ * F1. Userspace clears the rseq_cs field of the struct rseq
+ * TLS area. Followed by step [F2].
+ *
+ * [abort_ip]
+ * F2. Return false.
+ */
+
+static int rseq_increment_event_counter(struct task_struct *t)
+{
+ if (__put_user(++t->rseq_event_counter,
+ &t->rseq->u.e.event_counter))
+ return -1;
+ return 0;
+}
Given we want all 3 of those values in a single line and doing 3
get_user() calls ends up doing 3 pairs of STAC/CLAC, should we not use
either copy_from_user_inatomic or unsafe_get_user() paired with
user_access_begin/end() pairs.
Actually, we want copy_from_user() there. This executes upon
resume to user-space, so we can take a page fault is needed, so
no "inatomic" needed. I therefore suggest:
static bool rseq_get_rseq_cs(struct task_struct *t,
void __user **start_ip,
void __user **post_commit_ip,
void __user **abort_ip)
{
unsigned long ptr;
struct rseq_cs __user *urseq_cs;
struct rseq_cs rseq_cs;
if (__get_user(ptr, &t->rseq->rseq_cs))
return false;
if (!ptr)
return true;
#ifdef CONFIG_COMPAT
if (in_compat_syscall()) {
urseq_cs = compat_ptr((compat_uptr_t)ptr);
if (copy_from_user(&rseq_cs, urseq_cs, sizeof(*rseq_cs)))
return false;
*start_ip = compat_ptr((compat_uptr_t)rseq_cs.start_ip);
*post_commit_ip = compat_ptr((compat_uptr_t)rseq_cs.post_commit_ip);
*abort_ip = compat_ptr((compat_uptr_t)rseq_cs.abort_ip);
return true;
}
#endif
urseq_cs = (struct rseq_cs __user *)ptr;
if (copy_from_user(&rseq_cs, urseq_cs, sizeof(*rseq_cs)))
return false;
*start_ip = rseq_cs.start_ip;
*post_commit_ip = rseq_cs.post_commit_ip;
*abort_ip = rseq_cs.abort_ip;
return true;
}
quoted
+ *abort_ip = (void __user *)ptr;
+ return 0;
+}
this and,
ok. Will use bool.
quoted
+static int rseq_ip_fixup(struct pt_regs *regs)
+{
+ struct task_struct *t = current;
+ void __user *post_commit_ip = NULL;
+ void __user *abort_ip = NULL;
+
+ if (rseq_get_rseq_cs(t, &post_commit_ip, &abort_ip))
+ return -1;
+
+ /* Handle potentially being within a critical section. */
+ if ((void __user *)instruction_pointer(regs) < post_commit_ip) {
Alternatively you can do:
if (likely(void __user *)instruction_pointer(regs) >= post_commit_ip)
return 0;
and you can safe an indent level below.
ok. will do.
quoted
+ /*
+ * We need to clear rseq_cs upon entry into a signal
+ * handler nested on top of a rseq assembly block, so
+ * the signal handler will not be fixed up if itself
+ * interrupted by a nested signal handler or preempted.
+ */
+ if (clear_user(&t->rseq->rseq_cs,
+ sizeof(t->rseq->rseq_cs)))
+ return -1;
+
+ /*
+ * We set this after potentially failing in
+ * clear_user so that the signal arrives at the
+ * faulting rip.
+ */
+ instruction_pointer_set(regs, (unsigned long)abort_ip);
+ }
+ return 0;
+}
this function look like it should return bool.
ok. Will use bool.
quoted
+/*
+ * This resume handler should always be executed between any of:
+ * - preemption,
+ * - signal delivery,
+ * and return to user-space.
+ */
+void __rseq_handle_notify_resume(struct pt_regs *regs)
+{
+ struct task_struct *t = current;
+
+ if (unlikely(t->flags & PF_EXITING))
+ return;
+ if (!access_ok(VERIFY_WRITE, t->rseq, sizeof(*t->rseq)))
+ goto error;
+ if (__put_user(raw_smp_processor_id(), &t->rseq->u.e.cpu_id))
+ goto error;
+ if (rseq_increment_event_counter(t))
It seems a shame to not use a single __put_user() here. You did the
layout to explicitly allow for this, but then you don't.
The event counter increment needs to be performed at least once before
returning to user-space whenever the thread is preempted or has a signal
delivered. This counter increment needs to occur even if we are not nested
over a restartable assembly block. (more detailed explanation about this
follows at the end of this email)
The rseq_ip_fixup only ever needs to update the rseq_cs pointer
field if it preempts/delivers a signal over a restartable
assembly block, which happens very rarely.
Therefore, since the event counter increment is more frequent than
setting rseq_cs ptr, I don't see much value in trying to combine
those two into a single __put_user().
The reason why I combined both the cpu_id and event_counter
fields into the same 64-bit integer is for user-space rseq_start()
to be able to fetch them through a single load when the architecture
allows it.
+ if (!rseq) {
+ if (!current->rseq)
+ return -ENOENT;
+ return 0;
+ }
+
+ if (current->rseq) {
+ /*
+ * If rseq is already registered, check whether
+ * the provided address differs from the prior
+ * one.
+ */
+ if (current->rseq != rseq)
+ return -EBUSY;
Why explicitly allow resetting the same value?
The foreseen use is as follows: let's assume we have one or more
user-space libraries, and possibly the application, each using rseq.
They would each define a struct rseq TLS. They are expected to all
give it the same name (e.g. __rseq_thread_state), and mark it as a
weak symbol, so all uses of that symbol within the process address
space will refer to the same address for a given thread.
Registration of this TLS is done through a call to the rseq system
call. In cases where the application uses rseq, registration can be
done explicitly at thread creation by the application, since it controls
the beginning of the thread execution.
However, if we have uses in libraries that cannot rely on the application
registering the TLS, those libraries will need to lazily register their
struct rseq TLS the first time they use it within each thread.
So rather than to keep an extra flag in the __rseq_thread_state TLS
shared across application and various libs using rseq to indicate whether
it has been registered (with signal handler races it may involve if
rseq is used in a library within a signal handler), just allow the rseq
system call to succeed if multiple attempts are made to register the same
TLS address for a given thread.
One use-case I have in mind for libraries using rseq without requiring
the application to know about it is user-space tracing, as you would
have probably guessed. :)
quoted
+ } else {
+ /*
+ * If there was no rseq previously registered,
+ * we need to ensure the provided rseq is
+ * properly aligned and valid.
+ */
+ if (!IS_ALIGNED((unsigned long)rseq, sizeof(uint64_t)))
+ return -EINVAL;
+ if (!access_ok(VERIFY_WRITE, rseq, sizeof(*rseq)))
+ return -EFAULT;
GCC has __alignof__(struct rseq) for this. And as per the above, I would
recommend you change this to 2*sizeof(u64) to ensure the whole thing
fits in a single line.
Will use __alignof__(*rseq) for the IS_ALIGNED check, to match the
sizeof(*rseq) just below.
quoted
+ current->rseq = rseq;
+ /*
+ * If rseq was previously inactive, and has just
+ * been registered, ensure the cpu_id and
+ * event_counter fields are updated before
+ * returning to user-space.
+ */
+ rseq_set_notify_resume(current);
+ }
+
+ return 0;
+}
One thing I considered is doing something like:
static inline void rseq_sched_out(struct task_struct *t)
{
unsigned long ptr;
int err;
if (!t->rseq)
return;
err = __get_user(ptr, &t->rseq->rseq_cs);
if (err || ptr)
set_tsk_thread_flag(t, TIF_NOTIFY_RESUME);
}
That will optimistically try to read the rseq_cs pointer and, on success
and empty (the most likely case) avoid setting the TIF flag.
This will require an explicit migration hook to unconditionally set the
TIF flag such that we keep the cpu_id field correct of course.
And obviously we can do this later, as an optimization. Its just
something I figured might be worth it.
This won't work. The rseq mechanism proposed here is really the overlap
of _two_ distinct restart mechanisms: a sequence counter for C code,
and a ip-fixup-based mechanism for the assembly "finish" instruction
sequence.
What you propose here only considers the fixup of the assembly instruction
sequence, but not the C code that runs before. The C code between
rseq_start() and rseq_finish() loads the current value of the sequence
counter in rseq_start(), and then it gets compared with the new current
value within the rseq_finish restartable sequence of instructions. So the
sequence counter needs to be updated upon preemption/signal delivery that
occurs on top of C code, even if not nesting over a sequence of
restartable assembly instructions.
Thanks for the thorough review!
Mathieu
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-08-09 21:33:51
On Tue, Aug 09, 2016 at 08:06:40PM +0000, Mathieu Desnoyers wrote:
quoted
quoted
+static int rseq_increment_event_counter(struct task_struct *t)
+{
+ if (__put_user(++t->rseq_event_counter,
+ &t->rseq->u.e.event_counter))
+ return -1;
+ return 0;
+}
quoted
quoted
+void __rseq_handle_notify_resume(struct pt_regs *regs)
+{
+ struct task_struct *t = current;
+
+ if (unlikely(t->flags & PF_EXITING))
+ return;
+ if (!access_ok(VERIFY_WRITE, t->rseq, sizeof(*t->rseq)))
+ goto error;
+ if (__put_user(raw_smp_processor_id(), &t->rseq->u.e.cpu_id))
+ goto error;
+ if (rseq_increment_event_counter(t))
It seems a shame to not use a single __put_user() here. You did the
layout to explicitly allow for this, but then you don't.
The event counter increment needs to be performed at least once before
returning to user-space whenever the thread is preempted or has a signal
delivered. This counter increment needs to occur even if we are not nested
over a restartable assembly block. (more detailed explanation about this
follows at the end of this email)
The rseq_ip_fixup only ever needs to update the rseq_cs pointer
field if it preempts/delivers a signal over a restartable
assembly block, which happens very rarely.
Therefore, since the event counter increment is more frequent than
setting rseq_cs ptr, I don't see much value in trying to combine
those two into a single __put_user().
The reason why I combined both the cpu_id and event_counter
fields into the same 64-bit integer is for user-space rseq_start()
to be able to fetch them through a single load when the architecture
allows it.
I wasn't talking about the rseq_up_fixup(), I was talking about both
unconditional __put_user()'s on cpu_id and event_counter.
These are 2 unconditinoal u32 stores that could very easily be done as a
single u64 store (on 64bit hardware).
----- On Aug 9, 2016, at 5:33 PM, Peter Zijlstra peterz-wEGCiKHe2LqWVfeAwA7xHQ@public.gmane.org wrote:
On Tue, Aug 09, 2016 at 08:06:40PM +0000, Mathieu Desnoyers wrote:
quoted
quoted
quoted
+static int rseq_increment_event_counter(struct task_struct *t)
+{
+ if (__put_user(++t->rseq_event_counter,
+ &t->rseq->u.e.event_counter))
+ return -1;
+ return 0;
+}
quoted
quoted
quoted
+void __rseq_handle_notify_resume(struct pt_regs *regs)
+{
+ struct task_struct *t = current;
+
+ if (unlikely(t->flags & PF_EXITING))
+ return;
+ if (!access_ok(VERIFY_WRITE, t->rseq, sizeof(*t->rseq)))
+ goto error;
+ if (__put_user(raw_smp_processor_id(), &t->rseq->u.e.cpu_id))
+ goto error;
+ if (rseq_increment_event_counter(t))
It seems a shame to not use a single __put_user() here. You did the
layout to explicitly allow for this, but then you don't.
The event counter increment needs to be performed at least once before
returning to user-space whenever the thread is preempted or has a signal
delivered. This counter increment needs to occur even if we are not nested
over a restartable assembly block. (more detailed explanation about this
follows at the end of this email)
The rseq_ip_fixup only ever needs to update the rseq_cs pointer
field if it preempts/delivers a signal over a restartable
assembly block, which happens very rarely.
Therefore, since the event counter increment is more frequent than
setting rseq_cs ptr, I don't see much value in trying to combine
those two into a single __put_user().
The reason why I combined both the cpu_id and event_counter
fields into the same 64-bit integer is for user-space rseq_start()
to be able to fetch them through a single load when the architecture
allows it.
I wasn't talking about the rseq_up_fixup(), I was talking about both
unconditional __put_user()'s on cpu_id and event_counter.
These are 2 unconditinoal u32 stores that could very easily be done as a
single u64 store (on 64bit hardware).
Gotcha. I'll therefore move the union outside of struct rseq in rseq.h
so we can re-use it:
union rseq_cpu_event {
struct {
/*
* Restartable sequences cpu_id field.
* Updated by the kernel, and read by user-space with
* single-copy atomicity semantics. Aligned on 32-bit.
* Negative values are reserved for user-space.
*/
int32_t cpu_id;
/*
* Restartable sequences event_counter field.
* Updated by the kernel, and read by user-space with
* single-copy atomicity semantics. Aligned on 32-bit.
*/
uint32_t event_counter;
} e;
/*
* On architectures with 64-bit aligned reads, both cpu_id and
* event_counter can be read with single-copy atomicity
* semantics.
*/
uint64_t v;
};
/*
* struct rseq is aligned on 2 * 8 bytes to ensure it is always
* contained within a single cache-line.
*/
struct rseq {
union rseq_cpu_event u;
/*
* Restartable sequences rseq_cs field.
* Contains NULL when no critical section is active for the
* current thread, or holds a pointer to the currently active
* struct rseq_cs.
* Updated by user-space at the beginning and end of assembly
* instruction sequence block, and by the kernel when it
* restarts an assembly instruction sequence block. Read by the
* kernel with single-copy atomicity semantics. Aligned on
* 64-bit.
*/
RSEQ_FIELD_u32_u64(rseq_cs);
} __attribute__((aligned(2 * sizeof(uint64_t))));
I'll replace the two updates by this call in __rseq_handle_notify_resume():
if (!rseq_update_cpu_id_event_counter(t))
goto error;
And the given implementation:
/*
* The rseq_event_counter allow user-space to detect preemption and
* signal delivery. It increments at least once before returning to
* user-space if a thread is preempted or has a signal delivered. It is
* not meant to be an exact counter of such events.
*
* Overflow of the event counter is not a problem in practice. It
* increments at most once between each user-space thread instruction
* executed, so we would need a thread to execute 2^32 instructions or
* more between rseq_start() and rseq_finish(), while single-stepping,
* for this to be an issue.
*
* On 64-bit architectures, both cpu_id and event_counter can be updated
* with a single 64-bit store. On 32-bit architectures, we instead
* perform two 32-bit single-copy stores, just in case the architecture
* 64-bit __put_user() would fallback on a bytewise copy, which would
* not guarantee single-copy atomicity semantics for other threads.
*/
#ifdef __LP64__
static bool rseq_update_cpu_id_event_counter(struct task_struct *t)
{
union rseq_cpu_event u;
u.e.cpu_id = raw_smp_processor_id();
u.e.event_counter = ++t->rseq_event_counter;
if (__put_user(u.v, &t->rseq->u.v))
return false;
trace_rseq_inc(t->rseq_event_counter);
return true;
}
#else /* #ifdef __LP64__ */
static bool rseq_update_cpu_id_event_counter(struct task_struct *t)
{
if (__put_user(raw_smp_processor_id(), &t->rseq->u.e.cpu_id))
return false;
if (__put_user(++t->rseq_event_counter, &t->rseq->u.e.event_counter))
return false;
trace_rseq_inc(t->rseq_event_counter);
return true;
}
#endif /* #else #ifdef __LP64__ */
Let me know if I missed anything.
Thanks!
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
----- On Aug 10, 2016, at 4:43 AM, Peter Zijlstra peterz@infradead.org wrote:
On Tue, Aug 09, 2016 at 08:06:40PM +0000, Mathieu Desnoyers wrote:
<snip>
quoted
quoted
Also, I think it would be good to have a comment explaining why this is
split in two structures? Don't you rely on the address dependency?
The comment above the rseq_cs fields needs clarification, how about:
/*
* Restartable sequences rseq_cs field.
* Contains NULL when no critical section is active for the
* current thread, or holds a pointer to the currently active
* struct rseq_cs.
* Updated by user-space at the beginning and end of assembly
* instruction sequence block, and by the kernel when it
* restarts an assembly instruction sequence block. Read by the
* kernel with single-copy atomicity semantics. Aligned on
* 64-bit.
*/
This really explains that rseq_cs field of struct rseq holds a pointer
to the current struct rseq_cs (or NULL), which makes it obvious why this
needs to be two different structures.
I think I'm still missing things as its not obvious to me at all :/
We could equally well have chosen a single structure and picked the
post_commit_ip field to trigger things from, no?
The only down side seems to be that we must then impose ordering (but UP
ordering, so that's cheap) between writing the abort_ip and
post_commit_ip.
That is; something like so:
struct rseq {
union rseq_event_cpu u;
u64 abort_ip;
u64 post_commit_ip;
};
Where userspace must do:
r->abort_ip = $abort_ip;
barrier();
WRITE_ONCE(r->post_commit_ip, $post_commit_ip);
barrier();
Which is not much different from what Paul did, except he kept the
abort_ip in a register (which must be loaded before setting the
commit_ip).
And the kernel checks post_commit_ip, if 0, nothing happens, otherwise
we check instruction_pointer and do magic.
Then after the commit, we clear post_commit_ip again; just like we now
clear the rseq_cs pointer.
AFAICT this is an equally valid approach. So why split and put that
indirection in?
Now I understand from which angle you are looking at it.
The reason for this indirection is to speed up the user-space rseq_finish()
fast path:
With Paul Turner's approach, we needed to clobber a register, issue
instructions to move abort_ip to that register, and store the post_commit_ip
to the TLS.
With your approach here, you need 2 stores, ordered with compiler-barriers:
storing abort_ip to TLS, and then post_commit_ip to TLS.
The approach I propose (indirection) only requires a single store to the TLS:
we store the address of the currently active struct rseq_cs descriptor. The
kernel can then fetch the content of that descriptor (start_ip, post_commit_ip,
abort_ip) when/if it preempts/deliver a signal over that critical section.
On architectures like arm32, it makes a very significant difference
performance-wise to simply remove useless register movement or stores.
So I add an indirection in the kernel slow path (upon return to user-space after
preempting a rseq asm sequence, or upon signal delivery over a rseq asm sequence),
to speed up the user-space fast path.
By using the indirection approach, we also get the "start_ip" pointer for free,
which can be used to let the kernel know the exact range of the restartable
sequence, and means we can implement the abort handler in pure C, even if it
is placed at addresses before the restartable block by the compiler. This saves
us a jump on the fast path (otherwise required to skip over the abort code).
Doing the same with Paul's approach and yours would require to clobber yet
another register or add one more store for the start_ip.
quoted
Combined with other recent feedback, this becomes:
* The abort_ip address needs to be lesser than start_ip, or
Isn't it "less than" ?
Indeed, I had to look this one up. "lesser" is an adjective, and here
I should use "to be less than", but below the use the "be at addresses
lesser than" would appear to be OK.
quoted
* greater-or-equal the post_commit_ip. Step [4] and the failure
* code step [F1] need to be at addresses lesser than start_ip, or
* greater-or-equal the post_commit_ip.
----- On Aug 9, 2016, at 12:13 PM, Boqun Feng boqun.feng@gmail.com wrote:
<snip>
However, I'm thinking maybe we can use some tricks to avoid unnecessary
aborts-on-preemption.
First of all, I notice we haven't make any constraint on what kind of
memory objects could be "protected" by rseq critical sections yet. And I
think this is something we should decide before adding this feature into
kernel.
We can do some optimization if we have some constraints. For example, if
the memory objects inside the rseq critical sections could only be
modified by userspace programs, we therefore don't need to abort
immediately when userspace task -> kernel task context switch.
The rseq_owner per-cpu variable and rseq_cpu field in task_struct you
propose below would indeed take care of this scenario.
Further more, if the memory objects inside the rseq critical sections
could only be modified by userspace programs that have registered their
rseq structures, we don't need to abort immediately between the context
switches between two rseq-unregistered tasks or one rseq-registered
task and one rseq-unregistered task.
Instead, we do tricks as follow:
defining a percpu pointer in kernel:
DEFINE_PER_CPU(struct task_struct *, rseq_owner);
and a cpu field in struct task_struct:
struct task_struct {
...
#ifdef CONFIG_RSEQ
struct rseq __user *rseq;
uint32_t rseq_event_counter;
int rseq_cpu;
#endif
...
};
(task_struct::rseq_cpu should be initialized as -1.)
each time at sched out(in rseq_sched_out()), we do something like:
if (prev->rseq) {
raw_cpu_write(rseq_owner, prev);
prev->rseq_cpu = smp_processor_id();
}
each time sched in(in rseq_handle_notify_resume()), we do something
like:
if (current->rseq &&
(this_cpu_read(rseq_owner) != current ||
current->rseq_cpu != smp_processor_id()))
__rseq_handle_notify_resume(regs);
(Also need to modify rseq_signal_deliver() to call
__rseq_handle_notify_resume() directly).
I think this could save some unnecessary aborts-on-preemption, however,
TBH, I'm too sleepy to verify every corner case. Will recheck this
tomorrow.
This adds extra fields to the task struct, per-cpu rseq_owner pointers,
and hooks into sched_in which are not needed otherwise, all this to
eliminate unneeded abort-on-preemption.
If we look at the single-stepping use-case, this means that gdb would
only be able to single-step applications as long as neither itself, nor
any of its libraries, use rseq. This seems to be quite fragile. I prefer
requiring rseq users to implement a fallback to locking which progresses
in every situation rather than adding complexity and overhead trying
lessen the odds of triggering the restart.
Simply lessening the odds of triggering the restart without a design that
ensures progress even in restart cases seems to make the lack-of-progress
problem just harder to debug when it will surface in real life.
Thanks,
Mathieu
----- On Aug 10, 2016, at 4:01 AM, Andy Lutomirski luto@amacapital.net wrote:
On Tue, Aug 9, 2016 at 9:13 AM, Boqun Feng [off-list ref] wrote:
<snip>
quoted
However, I'm thinking maybe we can use some tricks to avoid unnecessary
aborts-on-preemption.
First of all, I notice we haven't make any constraint on what kind of
memory objects could be "protected" by rseq critical sections yet. And I
think this is something we should decide before adding this feature into
kernel.
We can do some optimization if we have some constraints. For example, if
the memory objects inside the rseq critical sections could only be
modified by userspace programs, we therefore don't need to abort
immediately when userspace task -> kernel task context switch.
True, although trying to do a syscall in an rseq critical section
seems like a bad idea in general.
The scenario above does not require the rseq critical section to perform
an explicit system call. It can happen from simple timer-driven preemption
of user-space.
<snip>
But do we need to protect MAP_SHARED objects? If not, maybe we could
only track context switches between different tasks sharing the same
mm.
I have tracing use-cases involving MAP_SHARED objects for rseq: per-cpu
buffers.
Moreover, if you only track context switch between tasks with the same
mm, you run into issues if you have:
Process A
Thread 1 (rseq)
Thread 2 (rseq)
Process B
Thread 1
Scheduling: A.1 -> B.1 -> A.2 -> B.1 -> A.1
There is no scheduling between threads of the same process here, but
the entire chain involves two threads of the same process accessing
the same per-cpu data concurrently.
Thanks,
Mathieu
----- On Aug 10, 2016, at 10:28 AM, Peter Zijlstra peterz@infradead.org wrote:
On Wed, Aug 10, 2016 at 01:57:05PM +0000, Mathieu Desnoyers wrote:
quoted
quoted
We could equally well have chosen a single structure and picked the
post_commit_ip field to trigger things from, no?
The only down side seems to be that we must then impose ordering (but UP
ordering, so that's cheap) between writing the abort_ip and
post_commit_ip.
That is; something like so:
struct rseq {
union rseq_event_cpu u;
u64 abort_ip;
u64 post_commit_ip;
};
Where userspace must do:
r->abort_ip = $abort_ip;
barrier();
WRITE_ONCE(r->post_commit_ip, $post_commit_ip);
barrier();
Which is not much different from what Paul did, except he kept the
abort_ip in a register (which must be loaded before setting the
commit_ip).
And the kernel checks post_commit_ip, if 0, nothing happens, otherwise
we check instruction_pointer and do magic.
Then after the commit, we clear post_commit_ip again; just like we now
clear the rseq_cs pointer.
AFAICT this is an equally valid approach. So why split and put that
indirection in?
Now I understand from which angle you are looking at it.
The reason for this indirection is to speed up the user-space rseq_finish()
fast path:
With Paul Turner's approach, we needed to clobber a register, issue
instructions to move abort_ip to that register, and store the post_commit_ip
to the TLS.
With your approach here, you need 2 stores, ordered with compiler-barriers:
storing abort_ip to TLS, and then post_commit_ip to TLS.
The approach I propose (indirection) only requires a single store to the TLS:
we store the address of the currently active struct rseq_cs descriptor. The
kernel can then fetch the content of that descriptor (start_ip, post_commit_ip,
abort_ip) when/if it preempts/deliver a signal over that critical section.
On architectures like arm32, it makes a very significant difference
performance-wise to simply remove useless register movement or stores.
So I add an indirection in the kernel slow path (upon return to user-space after
preempting a rseq asm sequence, or upon signal delivery over a rseq asm
sequence),
to speed up the user-space fast path.
By using the indirection approach, we also get the "start_ip" pointer for free,
which can be used to let the kernel know the exact range of the restartable
sequence, and means we can implement the abort handler in pure C, even if it
is placed at addresses before the restartable block by the compiler. This saves
us a jump on the fast path (otherwise required to skip over the abort code).
Doing the same with Paul's approach and yours would require to clobber yet
another register or add one more store for the start_ip.
Ah, because the {start,abort,commit} tuple is link time constants? Which
means we can have this in .data and not on the stack, avoiding the
stores entirely.
Yes, this is exactly what we do in the selftests rseq.h for x86 and ppc. For
ARM32, we put this in the code (we jump over it), so we can calculate the
address pointing to the descriptor using the ip-relative "adr" instruction,
which is faster than loading an arbitrary address constant.
Because the moment we put the thing on the stack, we need to do those
stores anyway.
Since those are link-time constants, we don't need to store them, ever.
Thanks,
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
One thing I considered is doing something like:
static inline void rseq_sched_out(struct task_struct *t)
{
unsigned long ptr;
int err;
if (!t->rseq)
return;
err = __get_user(ptr, &t->rseq->rseq_cs);
if (err || ptr)
set_tsk_thread_flag(t, TIF_NOTIFY_RESUME);
}
That will optimistically try to read the rseq_cs pointer and, on success
and empty (the most likely case) avoid setting the TIF flag.
This will require an explicit migration hook to unconditionally set the
TIF flag such that we keep the cpu_id field correct of course.
And obviously we can do this later, as an optimization. Its just
something I figured might be worth it.
This won't work. The rseq mechanism proposed here is really the overlap
of _two_ distinct restart mechanisms: a sequence counter for C code,
and a ip-fixup-based mechanism for the assembly "finish" instruction
sequence.
What you propose here only considers the fixup of the assembly instruction
sequence, but not the C code that runs before. The C code between
rseq_start() and rseq_finish() loads the current value of the sequence
counter in rseq_start(), and then it gets compared with the new current
value within the rseq_finish restartable sequence of instructions. So the
sequence counter needs to be updated upon preemption/signal delivery that
occurs on top of C code, even if not nesting over a sequence of
restartable assembly instructions.
True; we could of course have the rseq_start() also set a !0 state
before reading the seq, but not sure that all is worth it.
I don't think you need to guard it (and CONFIG_64BIT is the 'right'
kernel symbol for that), 32bit should have u64 __put_user() only
implemented as 2 u32 stores.
OK, I can then simplify the implementation to:
[...]
* On 64-bit architectures, both cpu_id and event_counter can be updated
* with a single 64-bit store. On 32-bit architectures, __put_user() is
* expected to perform two 32-bit single-copy stores to guarantee
* single-copy atomicity semantics for other threads.
*/
static bool rseq_update_cpu_id_event_counter(struct task_struct *t)
{
union rseq_cpu_event u;
u.e.cpu_id = raw_smp_processor_id();
u.e.event_counter = ++t->rseq_event_counter;
if (__put_user(u.v, &t->rseq->u.v))
return false;
trace_rseq_inc(t->rseq_event_counter);
return true;
}
Thanks!
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
I had not previously noticed the trace_* muck, but I would suggest
passing in t and leaving it up to the tracepoint implementation to pick
out the value.
OK, fixed.
Also, since this not only increments (it also updates the cpu number)
the naming is 'wrong'.
I'll rename the event to "rseq_update" then, and have two fields:
cpu_id and event_counter.
Thanks,
Mathieu
----- On Aug 10, 2016, at 4:10 AM, Andy Lutomirski luto-kltTT9wpgjJwATOyAt5JVQ@public.gmane.org wrote:
On Tue, Aug 9, 2016 at 1:06 PM, Mathieu Desnoyers
[off-list ref] wrote:
<snip>
quoted
Actually, we want copy_from_user() there. This executes upon
resume to user-space, so we can take a page fault is needed, so
no "inatomic" needed. I therefore suggest:
Running the code below via exit_to_usermode_loop...
...means that in_compat_syscall() is nonsense. (It *works* there, but
I can't imagine that it does anything that is actually sensible for
this use.)
Agreed that we are not per-se in a system call here. It works for
in_ia32_syscall(), but it may not work for in_x32_syscall().
Then should we test for this ?
if (!is_64bit_mm(current->mm))
This is currently x86-specific. Is this how we are expected to test
the user-space pointer size in the current mm in arch-agnostic code ?
If so, we should implement is_64bit_mm() on all other architectures.
Can't you just define the ABI so that no compat junk is needed?
(Also, CRIU will thank you for doing that.)
We are dealing with user-space pointers here, so AFAIU we need to
be aware of their size, which involves compat code. Am I missing
something ?
+ if (!rseq) {
+ if (!current->rseq)
+ return -ENOENT;
+ return 0;
+ }
This looks entirely wrong. Setting rseq to NULL fails if it's already
NULL but silently does nothing if rseq is already set? Surely it
should always succeed and it should actually do something if rseq is
set.
From the proposed rseq(2) manpage:
"A NULL rseq value can be used to check whether rseq is registered
for the current thread."
The implementation does just that: it returns -1, errno=ENOENT if no
rseq is currently registered, or 0 if rseq is currently registered.
Thanks,
Mathieu
From: Andy Lutomirski <luto@amacapital.net> Date: 2016-08-10 19:07:39
On Tue, Aug 9, 2016 at 9:13 AM, Boqun Feng [off-list ref] wrote:
On Wed, Aug 03, 2016 at 10:03:32PM -0700, Andy Lutomirski wrote:
quoted
On Wed, Aug 3, 2016 at 9:27 PM, Boqun Feng [off-list ref] wrote:
quoted
On Wed, Aug 03, 2016 at 09:37:57AM -0700, Andy Lutomirski wrote:
quoted
On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra [off-list ref] wrote:
quoted
On Tue, Jul 26, 2016 at 03:02:19AM +0000, Mathieu Desnoyers wrote:
quoted
We really care about preemption here. Every migration implies a
preemption from a user-space perspective. If we would only care
about keeping the CPU id up-to-date, hooking into migration would be
enough. But since we want atomicity guarantees for restartable
sequences, we need to hook into preemption.
quoted
It allows user-space to perform update operations on per-cpu data without
requiring heavy-weight atomic operations.
Well, a CMPXCHG without LOCK prefix isn't all that expensive on x86.
It is however on PPC and possibly other architectures, so in name of
simplicity supporting only the one variant makes sense.
I wouldn't want to depend on CMPXCHG. But imagine we had primitives
that were narrower than the full abort-on-preemption primitive.
Specifically, suppose we had abort if (actual cpu != expected_cpu ||
*aptr != aval). We could do things like:
expected_cpu = cpu;
aval = NULL; // disarm for now
begin();
aval = event_count[cpu] + 1;
event_count[cpu] = aval;
event_count[cpu]++;
This line is redundant, right? Because it will guarantee a failure even
in no-contention cases.
quoted
... compute something ...
// arm the rest of it
aptr = &event_count[cpu];
if (*aptr != aval)
goto fail;
*thing_im_writing = value_i_computed;
end();
The idea here is that we don't rely on the scheduler to increment the
event count at all, which means that we get to determine the scope of
what kinds of access conflicts we care about ourselves.
If we increase the event count in userspace, how could we prevent two
userspace threads from racing on the event_count[cpu] field? For
example:
CPU 0
================
{event_count[0] is initially 0}
[Thread 1]
begin();
aval = event_count[cpu] + 1; // 1
(preempted)
[Thread 2]
begin();
aval = event_count[cpu] + 1; // 1, too
event_count[cpu] = aval; // event_count[0] is 1
You're right :( This would work with an xadd instruction, but that's
very slow and doesn't exist on most architectures. It could also work
if we did:
aval = some_tls_value++;
where some_tls_value is set up such that no two threads could ever end
up with the same values (using high bits as thread ids, perhaps), but
that's messy. Maybe my idea is no good.
This is a little more complex, plus I failed to find a way to do an
atomic "if (*aptr == aval) *b = c" in userspace ;-(
But the kernel might be able to help using something similar to this patchset.
However, I'm thinking maybe we can use some tricks to avoid unnecessary
aborts-on-preemption.
First of all, I notice we haven't make any constraint on what kind of
memory objects could be "protected" by rseq critical sections yet. And I
think this is something we should decide before adding this feature into
kernel.
We can do some optimization if we have some constraints. For example, if
the memory objects inside the rseq critical sections could only be
modified by userspace programs, we therefore don't need to abort
immediately when userspace task -> kernel task context switch.
True, although trying to do a syscall in an rseq critical section
seems like a bad idea in general.
Further more, if the memory objects inside the rseq critical sections
could only be modified by userspace programs that have registered their
rseq structures, we don't need to abort immediately between the context
switches between two rseq-unregistered tasks or one rseq-registered
task and one rseq-unregistered task.
Instead, we do tricks as follow:
defining a percpu pointer in kernel:
DEFINE_PER_CPU(struct task_struct *, rseq_owner);
and a cpu field in struct task_struct:
struct task_struct {
...
#ifdef CONFIG_RSEQ
struct rseq __user *rseq;
uint32_t rseq_event_counter;
int rseq_cpu;
#endif
...
};
(task_struct::rseq_cpu should be initialized as -1.)
each time at sched out(in rseq_sched_out()), we do something like:
if (prev->rseq) {
raw_cpu_write(rseq_owner, prev);
prev->rseq_cpu = smp_processor_id();
}
each time sched in(in rseq_handle_notify_resume()), we do something
like:
if (current->rseq &&
(this_cpu_read(rseq_owner) != current ||
current->rseq_cpu != smp_processor_id()))
__rseq_handle_notify_resume(regs);
(Also need to modify rseq_signal_deliver() to call
__rseq_handle_notify_resume() directly).
I think this could save some unnecessary aborts-on-preemption, however,
TBH, I'm too sleepy to verify every corner case. Will recheck this
tomorrow.
Interesting. That could help a bit, although it would help less if
everyone started using rseq.
But do we need to protect MAP_SHARED objects? If not, maybe we could
only track context switches between different tasks sharing the same
mm.
--Andy
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-08-10 19:12:35
On Wed, Aug 10, 2016 at 01:57:05PM +0000, Mathieu Desnoyers wrote:
quoted
We could equally well have chosen a single structure and picked the
post_commit_ip field to trigger things from, no?
The only down side seems to be that we must then impose ordering (but UP
ordering, so that's cheap) between writing the abort_ip and
post_commit_ip.
That is; something like so:
struct rseq {
union rseq_event_cpu u;
u64 abort_ip;
u64 post_commit_ip;
};
Where userspace must do:
r->abort_ip = $abort_ip;
barrier();
WRITE_ONCE(r->post_commit_ip, $post_commit_ip);
barrier();
Which is not much different from what Paul did, except he kept the
abort_ip in a register (which must be loaded before setting the
commit_ip).
And the kernel checks post_commit_ip, if 0, nothing happens, otherwise
we check instruction_pointer and do magic.
Then after the commit, we clear post_commit_ip again; just like we now
clear the rseq_cs pointer.
AFAICT this is an equally valid approach. So why split and put that
indirection in?
Now I understand from which angle you are looking at it.
The reason for this indirection is to speed up the user-space rseq_finish()
fast path:
With Paul Turner's approach, we needed to clobber a register, issue
instructions to move abort_ip to that register, and store the post_commit_ip
to the TLS.
With your approach here, you need 2 stores, ordered with compiler-barriers:
storing abort_ip to TLS, and then post_commit_ip to TLS.
The approach I propose (indirection) only requires a single store to the TLS:
we store the address of the currently active struct rseq_cs descriptor. The
kernel can then fetch the content of that descriptor (start_ip, post_commit_ip,
abort_ip) when/if it preempts/deliver a signal over that critical section.
On architectures like arm32, it makes a very significant difference
performance-wise to simply remove useless register movement or stores.
So I add an indirection in the kernel slow path (upon return to user-space after
preempting a rseq asm sequence, or upon signal delivery over a rseq asm sequence),
to speed up the user-space fast path.
By using the indirection approach, we also get the "start_ip" pointer for free,
which can be used to let the kernel know the exact range of the restartable
sequence, and means we can implement the abort handler in pure C, even if it
is placed at addresses before the restartable block by the compiler. This saves
us a jump on the fast path (otherwise required to skip over the abort code).
Doing the same with Paul's approach and yours would require to clobber yet
another register or add one more store for the start_ip.
Ah, because the {start,abort,commit} tuple is link time constants? Which
means we can have this in .data and not on the stack, avoiding the
stores entirely.
Because the moment we put the thing on the stack, we need to do those
stores anyway.
I had not previously noticed the trace_* muck, but I would suggest
passing in t and leaving it up to the tracepoint implementation to pick
out the value.
Also, since this not only increments (it also updates the cpu number)
the naming is 'wrong'.
From: Andy Lutomirski <luto@amacapital.net> Date: 2016-08-10 19:16:34
On Wed, Aug 10, 2016 at 12:04 PM, Mathieu Desnoyers
[off-list ref] wrote:
----- On Aug 10, 2016, at 4:10 AM, Andy Lutomirski luto@amacapital.net wrote:
quoted
On Tue, Aug 9, 2016 at 1:06 PM, Mathieu Desnoyers
[off-list ref] wrote:
<snip>
quoted
quoted
Actually, we want copy_from_user() there. This executes upon
resume to user-space, so we can take a page fault is needed, so
no "inatomic" needed. I therefore suggest:
Running the code below via exit_to_usermode_loop...
...means that in_compat_syscall() is nonsense. (It *works* there, but
I can't imagine that it does anything that is actually sensible for
this use.)
Agreed that we are not per-se in a system call here. It works for
in_ia32_syscall(), but it may not work for in_x32_syscall().
Then should we test for this ?
if (!is_64bit_mm(current->mm))
This is currently x86-specific. Is this how we are expected to test
the user-space pointer size in the current mm in arch-agnostic code ?
If so, we should implement is_64bit_mm() on all other architectures.
There is no universal concept of the user-space pointer size on x86
because x86 code can change it via long jumps.
What are you actually trying to do? I would guess that
user_64bit_mode(regs) is the right thing here, because the rseq data
structure is describing the currently executing code.
quoted
Can't you just define the ABI so that no compat junk is needed?
(Also, CRIU will thank you for doing that.)
We are dealing with user-space pointers here, so AFAIU we need to
be aware of their size, which involves compat code. Am I missing
something ?
u64 is a perfectly valid, if odd, userspace pointer on all
architecures that I know of, and it's certainly a valid userspace
pointer on x86 32-bit userspace (the high bits will just all be zero).
Can you just use u64?
If this would be a performance problem on ARM, then maybe that's a
reason to use compat helpers.
+ if (!rseq) {
+ if (!current->rseq)
+ return -ENOENT;
+ return 0;
+ }
This looks entirely wrong. Setting rseq to NULL fails if it's already
NULL but silently does nothing if rseq is already set? Surely it
should always succeed and it should actually do something if rseq is
set.
From the proposed rseq(2) manpage:
"A NULL rseq value can be used to check whether rseq is registered
for the current thread."
The implementation does just that: it returns -1, errno=ENOENT if no
rseq is currently registered, or 0 if rseq is currently registered.
I think that's problematic. Why can't you unregister an existing
rseq? If you can't, how is a thread supposed to clean up after
itself?
--Andy
Maybe I missed it, but why do we want to hook into NOTIFY_RESUME and not
have our own TIF flag?
The short answer is that used the same approach as Paul Turner's patchset. ;)
Through a deeper look into this, the only times we set the flag is when
preempting and delivering a signal to a thread that has registered to
rseq.
Upon return to user-space with the flag set, the performance difference
between having our own flag and hopping into the NOTIFY_RESUME bandwagon
is that we can skip the various tests in exit_to_usermode_loop()
with our own flag, at the expense of crowding the thread flags even
nearer to filling up 32 bits, which will at some point require extra
tests on the fast-path.
I don't think we're anywhere near running out. Several of those flags
can probably go away pretty easily, too.
Thinking about it, one benchmark I have not done so far is to modify
hackbench so it registers its threads with the rseq system call. We
can then figure out whether reserving a flag for rseq is justified or
not.
Comparing 10 runs of hackbench registering its sender/receiver threads
with unmodified hackbench: (hackbench -l 100000)
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.7 defconfig+localyesconfig,
restartable sequences series applied.
Avg. Time (s) Std.dev. (s)
Unmodified Hackbench 40.5 0.1
Rseq-Registered Hackbench Threads 40.4 0.1
So initial results seems to indicate that adding the notify_resume
handling upon preemption does not have noticeable effects on
performance, so I don't consider it worthwhile to try optimizing
it by reserving its own thread flag. Or perhaps am I missing something
important here ?
I don't think so. One benefit of using do_notify_resume would be less
arch code.
Actually, we want copy_from_user() there. This executes upon
resume to user-space, so we can take a page fault is needed, so
no "inatomic" needed. I therefore suggest:
Running the code below via exit_to_usermode_loop...
...means that in_compat_syscall() is nonsense. (It *works* there, but
I can't imagine that it does anything that is actually sensible for
this use.)
Can't you just define the ABI so that no compat junk is needed?
(Also, CRIU will thank you for doing that.)
+ if (!rseq) {
+ if (!current->rseq)
+ return -ENOENT;
+ return 0;
+ }
This looks entirely wrong. Setting rseq to NULL fails if it's already
NULL but silently does nothing if rseq is already set? Surely it
should always succeed and it should actually do something if rseq is
set.
--
Andy Lutomirski
AMA Capital Management, LLC
From: Andy Lutomirski <luto@amacapital.net> Date: 2016-08-10 19:31:25
On Wed, Aug 3, 2016 at 10:03 PM, Andy Lutomirski [off-list ref] wrote:
On Wed, Aug 3, 2016 at 9:27 PM, Boqun Feng [off-list ref] wrote:
quoted
On Wed, Aug 03, 2016 at 09:37:57AM -0700, Andy Lutomirski wrote:
quoted
On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra [off-list ref] wrote:
quoted
On Tue, Jul 26, 2016 at 03:02:19AM +0000, Mathieu Desnoyers wrote:
quoted
We really care about preemption here. Every migration implies a
preemption from a user-space perspective. If we would only care
about keeping the CPU id up-to-date, hooking into migration would be
enough. But since we want atomicity guarantees for restartable
sequences, we need to hook into preemption.
quoted
It allows user-space to perform update operations on per-cpu data without
requiring heavy-weight atomic operations.
Well, a CMPXCHG without LOCK prefix isn't all that expensive on x86.
It is however on PPC and possibly other architectures, so in name of
simplicity supporting only the one variant makes sense.
I wouldn't want to depend on CMPXCHG. But imagine we had primitives
that were narrower than the full abort-on-preemption primitive.
Specifically, suppose we had abort if (actual cpu != expected_cpu ||
*aptr != aval). We could do things like:
expected_cpu = cpu;
aval = NULL; // disarm for now
begin();
aval = event_count[cpu] + 1;
event_count[cpu] = aval;
event_count[cpu]++;
This line is redundant, right? Because it will guarantee a failure even
in no-contention cases.
quoted
... compute something ...
// arm the rest of it
aptr = &event_count[cpu];
if (*aptr != aval)
goto fail;
*thing_im_writing = value_i_computed;
end();
The idea here is that we don't rely on the scheduler to increment the
event count at all, which means that we get to determine the scope of
what kinds of access conflicts we care about ourselves.
If we increase the event count in userspace, how could we prevent two
userspace threads from racing on the event_count[cpu] field? For
example:
CPU 0
================
{event_count[0] is initially 0}
[Thread 1]
begin();
aval = event_count[cpu] + 1; // 1
(preempted)
[Thread 2]
begin();
aval = event_count[cpu] + 1; // 1, too
event_count[cpu] = aval; // event_count[0] is 1
You're right :( This would work with an xadd instruction, but that's
very slow and doesn't exist on most architectures. It could also work
if we did:
Thinking about this slightly more, maybe it does work. We could use
basically the same mechanism to allow the kernel to restart if the
specific sequence:
aval = event_count[cpu] + 1
event_count[cpu] = avall
gets preempted by setting aptr = &event_count[cpu] and aval to
event_count[cpu], like this (although I might have screwed up any
number of small details):
aptr = &event_count[cpu];
barrier();
aval = event_count[cpu];
barrier();
tmp = aval + 1;
event_count[cpu] = tmp;
/* preemption here will cause an unnecessary retry, but that's okay */
aval = tmp;
--Andy
----- On Aug 3, 2016, at 2:29 PM, Chris Lameter cl-vYTEC60ixJUAvxtiuMwx3w@public.gmane.org wrote:
On Tue, 26 Jul 2016, Mathieu Desnoyers wrote:
quoted
quoted
What problem does this solve?
It allows user-space to perform update operations on per-cpu data without
requiring heavy-weight atomic operations.
This is great but seems to indicate that such a facility would be better
for kernel code instread of user space code.
It would be interesting to eventually investigate whether rseq is
additionally useful for kernel code. It seems unrelated to its usefulness
for user-space code though.
Rseq for user-space only needs to hook into preemption and signal delivery,
which doesn't seem to have measurable effects on overall performance.
Doing rseq for kernel code would imply hooking into supplementary sites:
- preemption of kernel code (for atomicity wrt other threads). This would
replace preempt_disable()/preempt_enable() critical sections touching
per-cpu data shared with other threads. We would have to do the event_counter
increment and ip fixup directly in the sched_out hook when preempting
kernel code.
- possibly interrupt handlers (for atomicity wrt interrupts). This would
replace local irq save/restore when touching per-cpu data shared with
interrupt handlers. We would have to increment the event_counter and
fixup on the pre-irq kernel frame.
- possibly NMI handlers (for atomicity wrt NMIs). This would replace
preempt/irq off protected local atomic operations on per-cpu data
shared with NMIs. We would have to increment the event_counter and
fixup on the pre-NMI kernel frame.
Those supplementary hooks may add significant overall performance overhead,
so careful benchmarking would be required to figure out if it's worth it.
quoted
First, prohibiting migration from user-space has been frowned upon
by scheduler developers for a long time, and I doubt this mindset will
change.
Note that the task isolation patchset from Chris Metcalf does something
that goes a long way towards this. If you set strict isolation mode then
the kernel will terminate the process or notify you if the scheduler
becomes involved. In some way we are getting that as a side effect.
AFAIU, what you propose here is doable at the application design level.
We want to introduce rseq to speed up memory allocation, tracing, and
other uses of per-cpu data without having to modify the design of each
and every user-space applications out there.
Also prohibiting migration is trivial form user space. Just do a taskset
to a single cpu.
This is also possible if you can redesign user-space applications, but not
from a library perspective. Invoking system calls to change the affinity of
a thread at each and every critical section would kill performance. Setting
the affinity of a thread from a library on behalf of the application and
leaving it affined requires changes to the application design.
Thanks,
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
I don't think you need to guard it (and CONFIG_64BIT is the 'right'
kernel symbol for that), 32bit should have u64 __put_user() only
implemented as 2 u32 stores.
----- On Aug 10, 2016, at 3:16 PM, Andy Lutomirski luto@amacapital.net wrote:
On Wed, Aug 10, 2016 at 12:04 PM, Mathieu Desnoyers
[off-list ref] wrote:
quoted
----- On Aug 10, 2016, at 4:10 AM, Andy Lutomirski luto@amacapital.net wrote:
quoted
On Tue, Aug 9, 2016 at 1:06 PM, Mathieu Desnoyers
[off-list ref] wrote:
<snip>
quoted
quoted
Actually, we want copy_from_user() there. This executes upon
resume to user-space, so we can take a page fault is needed, so
no "inatomic" needed. I therefore suggest:
Running the code below via exit_to_usermode_loop...
...means that in_compat_syscall() is nonsense. (It *works* there, but
I can't imagine that it does anything that is actually sensible for
this use.)
Agreed that we are not per-se in a system call here. It works for
in_ia32_syscall(), but it may not work for in_x32_syscall().
Then should we test for this ?
if (!is_64bit_mm(current->mm))
This is currently x86-specific. Is this how we are expected to test
the user-space pointer size in the current mm in arch-agnostic code ?
If so, we should implement is_64bit_mm() on all other architectures.
There is no universal concept of the user-space pointer size on x86
because x86 code can change it via long jumps.
What are you actually trying to do? I would guess that
user_64bit_mode(regs) is the right thing here, because the rseq data
structure is describing the currently executing code.
Yes, that's correct, we care about the pointer size of currently executing
code. On x86 user_64bit_mode(regs) would appear to be the right thing to do.
quoted
quoted
Can't you just define the ABI so that no compat junk is needed?
(Also, CRIU will thank you for doing that.)
We are dealing with user-space pointers here, so AFAIU we need to
be aware of their size, which involves compat code. Am I missing
something ?
u64 is a perfectly valid, if odd, userspace pointer on all
architecures that I know of, and it's certainly a valid userspace
pointer on x86 32-bit userspace (the high bits will just all be zero).
Can you just use u64?
My concern is about a 32-bit user-space putting garbage rather than zeroes
(on purpose) to fool the kernel on those upper 32 bits. Doing
compat_ptr((compat_uptr_t)rseq_cs.start_ip)
effectively ends up clearing the upper 32 bits.
But since we only use those pointer values for comparisons, perhaps we
just don't care if a 32-bit userspace app try to shoot itself in
the foot by passing garbage upper 32 bits ?
If this would be a performance problem on ARM, then maybe that's a
reason to use compat helpers.
We already use 64-bit values for the pointers, even on 32-bit. Normally
userspace just puts zeroes in the top bits. It's mostly a question of
clearing the top 32 bits or not when loading them in the kernel. If we
don't need to, then I can remove the compat code entirely, and we don't
care about user_64bit_mode() anymore, as you initially recommended.
Does it make sense ?
+ if (!rseq) {
+ if (!current->rseq)
+ return -ENOENT;
+ return 0;
+ }
This looks entirely wrong. Setting rseq to NULL fails if it's already
NULL but silently does nothing if rseq is already set? Surely it
should always succeed and it should actually do something if rseq is
set.
From the proposed rseq(2) manpage:
"A NULL rseq value can be used to check whether rseq is registered
for the current thread."
The implementation does just that: it returns -1, errno=ENOENT if no
rseq is currently registered, or 0 if rseq is currently registered.
I think that's problematic. Why can't you unregister an existing
rseq? If you can't, how is a thread supposed to clean up after
itself?
Unregistering an existing thread rseq would require that we keep reference
counting, in case multiple libs and/or the app are using rseq. I am
trying to keep things as simple as needed.
If I understand your concern, the problematic scenario would be at
thread exit (this is my current approximate understanding of glibc
handling of library TLS variable reclaim at thread exit):
thread exits in userspace:
- glibc frees its rseq TLS memory area (in case the TLS is in a library),
- thread preempted before really exiting,
- kernel reads/writes to freed TLS memory.
- corruption may occur (e.g. memory re-allocated by another thread already)
Am I getting it right ?
Thanks,
Mathieu
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-08-10 20:08:09
On Tue, Aug 09, 2016 at 08:06:40PM +0000, Mathieu Desnoyers wrote:
quoted
Also, do we want a comment somewhere that explains why overflow isn't a
problem?
I can add a comment about rseq_increment_event_counter stating:
* Overflow of the event counter is not a problem in practice. It
* increments at most once between each user-space thread instruction
* executed, so we would need a thread to execute 2^32 instructions or
* more between rseq_start() and rseq_finish(), while single-stepping,
* for this to be an issue.
Is it fine, or should we be more conservative and care about the overflow,
extending the counter to a 64-bit value in the process ?
I think its good enough; and using u64 has the unfortunate side effect
of not being able to share the word with the cpu number.
My point was more to have this stuff clearly documented.
quoted
Maybe I missed it, but why do we want to hook into NOTIFY_RESUME and not
have our own TIF flag?
The short answer is that used the same approach as Paul Turner's patchset. ;)
Through a deeper look into this, the only times we set the flag is when
preempting and delivering a signal to a thread that has registered to
rseq.
<snip>
So initial results seems to indicate that adding the notify_resume
handling upon preemption does not have noticeable effects on
performance, so I don't consider it worthwhile to try optimizing
it by reserving its own thread flag. Or perhaps am I missing something
important here ?
Not sure; seems like we can leave it as is for the moment. Again my
point was to make sure we've thought about the decision, and per the
above you clearly have now ;-)
quoted
Also, I think it would be good to have a comment explaining why this is
split in two structures? Don't you rely on the address dependency?
The comment above the rseq_cs fields needs clarification, how about:
/*
* Restartable sequences rseq_cs field.
* Contains NULL when no critical section is active for the
* current thread, or holds a pointer to the currently active
* struct rseq_cs.
* Updated by user-space at the beginning and end of assembly
* instruction sequence block, and by the kernel when it
* restarts an assembly instruction sequence block. Read by the
* kernel with single-copy atomicity semantics. Aligned on
* 64-bit.
*/
This really explains that rseq_cs field of struct rseq holds a pointer
to the current struct rseq_cs (or NULL), which makes it obvious why this
needs to be two different structures.
I think I'm still missing things as its not obvious to me at all :/
We could equally well have chosen a single structure and picked the
post_commit_ip field to trigger things from, no?
The only down side seems to be that we must then impose ordering (but UP
ordering, so that's cheap) between writing the abort_ip and
post_commit_ip.
That is; something like so:
struct rseq {
union rseq_event_cpu u;
u64 abort_ip;
u64 post_commit_ip;
};
Where userspace must do:
r->abort_ip = $abort_ip;
barrier();
WRITE_ONCE(r->post_commit_ip, $post_commit_ip);
barrier();
Which is not much different from what Paul did, except he kept the
abort_ip in a register (which must be loaded before setting the
commit_ip).
And the kernel checks post_commit_ip, if 0, nothing happens, otherwise
we check instruction_pointer and do magic.
Then after the commit, we clear post_commit_ip again; just like we now
clear the rseq_cs pointer.
AFAICT this is an equally valid approach. So why split and put that
indirection in?
Combined with other recent feedback, this becomes:
* The abort_ip address needs to be lesser than start_ip, or
Isn't it "less than" ?
* greater-or-equal the post_commit_ip. Step [4] and the failure
* code step [F1] need to be at addresses lesser than start_ip, or
* greater-or-equal the post_commit_ip.
quoted
quoted
+ if (current->rseq) {
+ /*
+ * If rseq is already registered, check whether
+ * the provided address differs from the prior
+ * one.
+ */
+ if (current->rseq != rseq)
+ return -EBUSY;
Why explicitly allow resetting the same value?
The foreseen use is as follows: let's assume we have one or more
user-space libraries, and possibly the application, each using rseq.
They would each define a struct rseq TLS. They are expected to all
give it the same name (e.g. __rseq_thread_state), and mark it as a
weak symbol, so all uses of that symbol within the process address
space will refer to the same address for a given thread.
From: Andy Lutomirski <luto@amacapital.net> Date: 2016-08-10 20:10:22
On Wed, Aug 10, 2016 at 1:06 PM, Mathieu Desnoyers
[off-list ref] wrote:
----- On Aug 10, 2016, at 3:16 PM, Andy Lutomirski luto-kltTT9wpgjJwATOyAt5JVQ@public.gmane.org wrote:
quoted
On Wed, Aug 10, 2016 at 12:04 PM, Mathieu Desnoyers
[off-list ref] wrote:
quoted
----- On Aug 10, 2016, at 4:10 AM, Andy Lutomirski luto-kltTT9wpgjJwATOyAt5JVQ@public.gmane.org wrote:
quoted
On Tue, Aug 9, 2016 at 1:06 PM, Mathieu Desnoyers
[off-list ref] wrote:
<snip>
quoted
quoted
Actually, we want copy_from_user() there. This executes upon
resume to user-space, so we can take a page fault is needed, so
no "inatomic" needed. I therefore suggest:
Running the code below via exit_to_usermode_loop...
...means that in_compat_syscall() is nonsense. (It *works* there, but
I can't imagine that it does anything that is actually sensible for
this use.)
Agreed that we are not per-se in a system call here. It works for
in_ia32_syscall(), but it may not work for in_x32_syscall().
Then should we test for this ?
if (!is_64bit_mm(current->mm))
This is currently x86-specific. Is this how we are expected to test
the user-space pointer size in the current mm in arch-agnostic code ?
If so, we should implement is_64bit_mm() on all other architectures.
There is no universal concept of the user-space pointer size on x86
because x86 code can change it via long jumps.
What are you actually trying to do? I would guess that
user_64bit_mode(regs) is the right thing here, because the rseq data
structure is describing the currently executing code.
Yes, that's correct, we care about the pointer size of currently executing
code. On x86 user_64bit_mode(regs) would appear to be the right thing to do.
quoted
quoted
quoted
Can't you just define the ABI so that no compat junk is needed?
(Also, CRIU will thank you for doing that.)
We are dealing with user-space pointers here, so AFAIU we need to
be aware of their size, which involves compat code. Am I missing
something ?
u64 is a perfectly valid, if odd, userspace pointer on all
architecures that I know of, and it's certainly a valid userspace
pointer on x86 32-bit userspace (the high bits will just all be zero).
Can you just use u64?
My concern is about a 32-bit user-space putting garbage rather than zeroes
(on purpose) to fool the kernel on those upper 32 bits. Doing
compat_ptr((compat_uptr_t)rseq_cs.start_ip)
effectively ends up clearing the upper 32 bits.
But since we only use those pointer values for comparisons, perhaps we
just don't care if a 32-bit userspace app try to shoot itself in
the foot by passing garbage upper 32 bits ?
How is garbage in the high bits any different than garbage in any
other bits in there?
quoted
If this would be a performance problem on ARM, then maybe that's a
reason to use compat helpers.
We already use 64-bit values for the pointers, even on 32-bit. Normally
userspace just puts zeroes in the top bits. It's mostly a question of
clearing the top 32 bits or not when loading them in the kernel. If we
don't need to, then I can remove the compat code entirely, and we don't
care about user_64bit_mode() anymore, as you initially recommended.
Does it make sense ?
Yes, I think so. I'd suggest just honoring all the bits.
+ if (!rseq) {
+ if (!current->rseq)
+ return -ENOENT;
+ return 0;
+ }
This looks entirely wrong. Setting rseq to NULL fails if it's already
NULL but silently does nothing if rseq is already set? Surely it
should always succeed and it should actually do something if rseq is
set.
From the proposed rseq(2) manpage:
"A NULL rseq value can be used to check whether rseq is registered
for the current thread."
The implementation does just that: it returns -1, errno=ENOENT if no
rseq is currently registered, or 0 if rseq is currently registered.
I think that's problematic. Why can't you unregister an existing
rseq? If you can't, how is a thread supposed to clean up after
itself?
Unregistering an existing thread rseq would require that we keep reference
counting, in case multiple libs and/or the app are using rseq. I am
trying to keep things as simple as needed.
If I understand your concern, the problematic scenario would be at
thread exit (this is my current approximate understanding of glibc
handling of library TLS variable reclaim at thread exit):
thread exits in userspace:
- glibc frees its rseq TLS memory area (in case the TLS is in a library),
- thread preempted before really exiting,
- kernel reads/writes to freed TLS memory.
- corruption may occur (e.g. memory re-allocated by another thread already)
Am I getting it right ?
From: Christoph Lameter <hidden> Date: 2016-08-10 20:38:29
On Wed, 10 Aug 2016, Mathieu Desnoyers wrote:
- preemption of kernel code (for atomicity wrt other threads). This would
replace preempt_disable()/preempt_enable() critical sections touching
per-cpu data shared with other threads. We would have to do the event_counter
increment and ip fixup directly in the sched_out hook when preempting
kernel code.
What we would need is special handling when returning from a context
switch so that we recognize in what type of code section we are in and
continue execution at the proper retry site. This can be done by putting
code into special sections or other methods that do not require additional
coee.
- possibly interrupt handlers (for atomicity wrt interrupts). This would
replace local irq save/restore when touching per-cpu data shared with
interrupt handlers. We would have to increment the event_counter and
fixup on the pre-irq kernel frame.
Same thing as before. Test if we are in a section by testing the return
address and then maybe continue elsewhere.
Those supplementary hooks may add significant overall performance overhead,
so careful benchmarking would be required to figure out if it's worth it.
We need a design that does not need these hooks. If we check the return
IP address for a special range then we would not need those. Any hooks
would bloat the code in such a way that the implementation would not be
acceptable for the kernel code.
----- On Aug 10, 2016, at 4:09 PM, Andy Lutomirski luto@amacapital.net wrote:
On Wed, Aug 10, 2016 at 1:06 PM, Mathieu Desnoyers [off-list ref] wrote:
<snip>
quoted
quoted
u64 is a perfectly valid, if odd, userspace pointer on all
architecures that I know of, and it's certainly a valid userspace
pointer on x86 32-bit userspace (the high bits will just all be zero).
Can you just use u64?
My concern is about a 32-bit user-space putting garbage rather than zeroes
(on purpose) to fool the kernel on those upper 32 bits. Doing
compat_ptr((compat_uptr_t)rseq_cs.start_ip)
effectively ends up clearing the upper 32 bits.
But since we only use those pointer values for comparisons, perhaps we
just don't care if a 32-bit userspace app try to shoot itself in
the foot by passing garbage upper 32 bits ?
How is garbage in the high bits any different than garbage in any
other bits in there?
It's not :)
quoted
quoted
If this would be a performance problem on ARM, then maybe that's a
reason to use compat helpers.
We already use 64-bit values for the pointers, even on 32-bit. Normally
userspace just puts zeroes in the top bits. It's mostly a question of
clearing the top 32 bits or not when loading them in the kernel. If we
don't need to, then I can remove the compat code entirely, and we don't
care about user_64bit_mode() anymore, as you initially recommended.
Does it make sense ?
Yes, I think so. I'd suggest just honoring all the bits.
+ if (!rseq) {
+ if (!current->rseq)
+ return -ENOENT;
+ return 0;
+ }
This looks entirely wrong. Setting rseq to NULL fails if it's already
NULL but silently does nothing if rseq is already set? Surely it
should always succeed and it should actually do something if rseq is
set.
From the proposed rseq(2) manpage:
"A NULL rseq value can be used to check whether rseq is registered
for the current thread."
The implementation does just that: it returns -1, errno=ENOENT if no
rseq is currently registered, or 0 if rseq is currently registered.
I think that's problematic. Why can't you unregister an existing
rseq? If you can't, how is a thread supposed to clean up after
itself?
Unregistering an existing thread rseq would require that we keep reference
counting, in case multiple libs and/or the app are using rseq. I am
trying to keep things as simple as needed.
If I understand your concern, the problematic scenario would be at
thread exit (this is my current approximate understanding of glibc
handling of library TLS variable reclaim at thread exit):
thread exits in userspace:
- glibc frees its rseq TLS memory area (in case the TLS is in a library),
- thread preempted before really exiting,
- kernel reads/writes to freed TLS memory.
- corruption may occur (e.g. memory re-allocated by another thread already)
Am I getting it right ?
Yes.
Hrm, then we should:
- add a rseq_refcount field to the task struct,
- increment this refcount whenever rseq receives a registration, after
ensuring that we are registering the same address as was previously
requested by preceding registrations for the thread (except if the
refcount was 0),
- When rseq receives a NULL address, decrement refcount. Set address to
NULL when it reaches 0.
Doing the refcounting in kernel-space rather than user-space allows us to
keep both registration/unregistration and refcount atomic, which simplify
things if we plan to use rseq from signal handlers.
With current glibc, a library that would lazily register and use rseq
without knowledge of the application would then have to use pthread_key_create()
to set a destr_function to run at thread exit, which would take care of
unregistration.
We could add a RSEQ_FORCE_UNREGISTER flag to rseq flags to allow future
glibc versions to force unregistering rseq before freeing its TLS memory,
just in case a userspace library omits to unregister itself.
Thoughts ?
Thanks,
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
On Wed, Aug 10, 2016 at 05:33:44PM +0000, Mathieu Desnoyers wrote:
----- On Aug 9, 2016, at 12:13 PM, Boqun Feng boqun.feng-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org wrote:
<snip>
quoted
However, I'm thinking maybe we can use some tricks to avoid unnecessary
aborts-on-preemption.
First of all, I notice we haven't make any constraint on what kind of
memory objects could be "protected" by rseq critical sections yet. And I
think this is something we should decide before adding this feature into
kernel.
We can do some optimization if we have some constraints. For example, if
the memory objects inside the rseq critical sections could only be
modified by userspace programs, we therefore don't need to abort
immediately when userspace task -> kernel task context switch.
The rseq_owner per-cpu variable and rseq_cpu field in task_struct you
propose below would indeed take care of this scenario.
quoted
Further more, if the memory objects inside the rseq critical sections
could only be modified by userspace programs that have registered their
rseq structures, we don't need to abort immediately between the context
switches between two rseq-unregistered tasks or one rseq-registered
task and one rseq-unregistered task.
Instead, we do tricks as follow:
defining a percpu pointer in kernel:
DEFINE_PER_CPU(struct task_struct *, rseq_owner);
and a cpu field in struct task_struct:
struct task_struct {
...
#ifdef CONFIG_RSEQ
struct rseq __user *rseq;
uint32_t rseq_event_counter;
int rseq_cpu;
#endif
...
};
(task_struct::rseq_cpu should be initialized as -1.)
each time at sched out(in rseq_sched_out()), we do something like:
if (prev->rseq) {
raw_cpu_write(rseq_owner, prev);
prev->rseq_cpu = smp_processor_id();
}
each time sched in(in rseq_handle_notify_resume()), we do something
like:
if (current->rseq &&
(this_cpu_read(rseq_owner) != current ||
current->rseq_cpu != smp_processor_id()))
__rseq_handle_notify_resume(regs);
(Also need to modify rseq_signal_deliver() to call
__rseq_handle_notify_resume() directly).
I think this could save some unnecessary aborts-on-preemption, however,
TBH, I'm too sleepy to verify every corner case. Will recheck this
tomorrow.
This adds extra fields to the task struct, per-cpu rseq_owner pointers,
and hooks into sched_in which are not needed otherwise, all this to
eliminate unneeded abort-on-preemption.
If we look at the single-stepping use-case, this means that gdb would
only be able to single-step applications as long as neither itself, nor
any of its libraries, use rseq. This seems to be quite fragile. I prefer
requiring rseq users to implement a fallback to locking which progresses
in every situation rather than adding complexity and overhead trying
lessen the odds of triggering the restart.
Simply lessening the odds of triggering the restart without a design that
ensures progress even in restart cases seems to make the lack-of-progress
problem just harder to debug when it will surface in real life.
Fair enough.
I did my own research of the mechanism I proposed. The patch is attached
at the end of the email. Unfortunately, there is no noticeable
performance gain for the current benchmark. One possible reason may be:
The rseq critical sections in current benchmark are quite small, which
makes retrying is not that expensive.
From another angle, this may imply that in current senarios,
abort-on-preemption doesn't hurt the performance much. But these are
only my two cents.
@@ -1922,6 +1922,7 @@ struct task_struct {#ifdef CONFIG_RSEQstructrseq__user*rseq;u32rseq_event_counter;+intrseq_cpu;#endif/* CPU-specific state of this task */structthread_structthread;
From: Andy Lutomirski <luto@amacapital.net> Date: 2016-08-11 07:23:45
On Aug 11, 2016 12:01 AM, "Mathieu Desnoyers"
[off-list ref] wrote:
----- On Aug 10, 2016, at 4:09 PM, Andy Lutomirski luto-kltTT9wpgjJwATOyAt5JVQ@public.gmane.org wrote:
quoted
On Wed, Aug 10, 2016 at 1:06 PM, Mathieu Desnoyers [off-list ref] wrote:
<snip>
quoted
quoted
quoted
u64 is a perfectly valid, if odd, userspace pointer on all
architecures that I know of, and it's certainly a valid userspace
pointer on x86 32-bit userspace (the high bits will just all be zero).
Can you just use u64?
My concern is about a 32-bit user-space putting garbage rather than zeroes
(on purpose) to fool the kernel on those upper 32 bits. Doing
compat_ptr((compat_uptr_t)rseq_cs.start_ip)
effectively ends up clearing the upper 32 bits.
But since we only use those pointer values for comparisons, perhaps we
just don't care if a 32-bit userspace app try to shoot itself in
the foot by passing garbage upper 32 bits ?
How is garbage in the high bits any different than garbage in any
other bits in there?
It's not :)
quoted
quoted
quoted
If this would be a performance problem on ARM, then maybe that's a
reason to use compat helpers.
We already use 64-bit values for the pointers, even on 32-bit. Normally
userspace just puts zeroes in the top bits. It's mostly a question of
clearing the top 32 bits or not when loading them in the kernel. If we
don't need to, then I can remove the compat code entirely, and we don't
care about user_64bit_mode() anymore, as you initially recommended.
Does it make sense ?
Yes, I think so. I'd suggest just honoring all the bits.
+ if (!rseq) {
+ if (!current->rseq)
+ return -ENOENT;
+ return 0;
+ }
This looks entirely wrong. Setting rseq to NULL fails if it's already
NULL but silently does nothing if rseq is already set? Surely it
should always succeed and it should actually do something if rseq is
set.
From the proposed rseq(2) manpage:
"A NULL rseq value can be used to check whether rseq is registered
for the current thread."
The implementation does just that: it returns -1, errno=ENOENT if no
rseq is currently registered, or 0 if rseq is currently registered.
I think that's problematic. Why can't you unregister an existing
rseq? If you can't, how is a thread supposed to clean up after
itself?
Unregistering an existing thread rseq would require that we keep reference
counting, in case multiple libs and/or the app are using rseq. I am
trying to keep things as simple as needed.
If I understand your concern, the problematic scenario would be at
thread exit (this is my current approximate understanding of glibc
handling of library TLS variable reclaim at thread exit):
thread exits in userspace:
- glibc frees its rseq TLS memory area (in case the TLS is in a library),
- thread preempted before really exiting,
- kernel reads/writes to freed TLS memory.
- corruption may occur (e.g. memory re-allocated by another thread already)
Am I getting it right ?
Yes.
Hrm, then we should:
- add a rseq_refcount field to the task struct,
- increment this refcount whenever rseq receives a registration, after
ensuring that we are registering the same address as was previously
requested by preceding registrations for the thread (except if the
refcount was 0),
- When rseq receives a NULL address, decrement refcount. Set address to
NULL when it reaches 0.
Doing the refcounting in kernel-space rather than user-space allows us to
keep both registration/unregistration and refcount atomic, which simplify
things if we plan to use rseq from signal handlers.
With current glibc, a library that would lazily register and use rseq
without knowledge of the application would then have to use pthread_key_create()
to set a destr_function to run at thread exit, which would take care of
unregistration.
That sounds reasonable at first glance.
We could add a RSEQ_FORCE_UNREGISTER flag to rseq flags to allow future
glibc versions to force unregistering rseq before freeing its TLS memory,
just in case a userspace library omits to unregister itself.