Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1466651 > unrolled thread

[RFC PATCH v8 0/9] Restartable sequences system call

Back to article view | Back to linux.kernel

Contents

  [RFC PATCH v8 0/9] Restartable sequences system call Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-08-19 22:20 +0200
    [RFC PATCH v8 6/9] Restartable sequences: wire up x86 32/64 system call Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-08-19 22:20 +0200
    [RFC PATCH v8 2/9] tracing: instrument restartable sequences Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-08-19 22:20 +0200
    Re: [RFC PATCH v8 1/9] Restartable sequences system call Linus Torvalds <torvalds@linux-foundation.org> - 2016-08-19 22:30 +0200
      Re: [RFC PATCH v8 1/9] Restartable sequences system call Andi Kleen <andi@firstfloor.org> - 2016-08-19 23:00 +0200
        Re: [RFC PATCH v8 1/9] Restartable sequences system call "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-08-19 23:20 +0200
          Re: [RFC PATCH v8 1/9] Restartable sequences system call Linus Torvalds <torvalds@linux-foundation.org> - 2016-08-19 23:50 +0200
            Re: [RFC PATCH v8 1/9] Restartable sequences system call "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-08-20 01:40 +0200
        Re: [RFC PATCH v8 1/9] Restartable sequences system call Josh Triplett <josh@joshtriplett.org> - 2016-08-19 23:30 +0200
      Re: [RFC PATCH v8 1/9] Restartable sequences system call Josh Triplett <josh@joshtriplett.org> - 2016-08-19 23:00 +0200
        Re: [RFC PATCH v8 1/9] Restartable sequences system call Linus Torvalds <torvalds@linux-foundation.org> - 2016-08-19 23:20 +0200
      Re: [RFC PATCH v8 1/9] Restartable sequences system call Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-08-25 19:10 +0200
        Re: [RFC PATCH v8 1/9] Restartable sequences system call Ben Maurer <bmaurer@fb.com> - 2016-08-25 20:00 +0200
          Re: [RFC PATCH v8 1/9] Restartable sequences system call Josh Triplett <josh@joshtriplett.org> - 2016-08-27 06:40 +0200
            Re: [RFC PATCH v8 1/9] Restartable sequences system call Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-08-29 17:20 +0200
              Re: [RFC PATCH v8 1/9] Restartable sequences system call Josh Triplett <josh@joshtriplett.org> - 2016-08-29 18:20 +0200
              Re: [RFC PATCH v8 1/9] Restartable sequences system call Boqun Feng <boqun.feng@gmail.com> - 2016-08-30 04:10 +0200

#1466651 — [RFC PATCH v8 0/9] Restartable sequences system call

Hi,

Here is v8 of the restartable sequences system call patchset, after
taking care of feedback received from Peter Zijlstra, Andy Lutomirski,
Boqun Feng, and Dave Watson. Added PowerPC architecture support provided
by Boqun Feng. It is based on Linux kernel v4.8-rc2.

The small library provided in kernel selftests now allows to perform
either a single final commit (do_rseq()), a speculative store before the
final commit (do_rseq2()), or a speculative memcpy before the final
commit (do_rseq_memcpy()).

Feedback is welcome!

Thanks,

Mathieu

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

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                                        |   11 +
 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/powerpc/Kconfig                               |    1 +
 arch/powerpc/include/asm/systbl.h                  |    1 +
 arch/powerpc/include/asm/unistd.h                  |    2 +-
 arch/powerpc/include/uapi/asm/unistd.h             |    1 +
 arch/powerpc/kernel/signal.c                       |    3 +
 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                              |   72 ++
 include/trace/events/rseq.h                        |   64 ++
 include/uapi/linux/Kbuild                          |    1 +
 include/uapi/linux/rseq.h                          |  106 ++
 init/Kconfig                                       |   13 +
 kernel/Makefile                                    |    1 +
 kernel/fork.c                                      |    2 +
 kernel/rseq.c                                      |  296 ++++++
 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 |  286 +++++
 tools/testing/selftests/rseq/basic_test.c          |  107 ++
 tools/testing/selftests/rseq/param_test.c          | 1116 ++++++++++++++++++++
 tools/testing/selftests/rseq/rseq-arm.h            |  168 +++
 tools/testing/selftests/rseq/rseq-ppc.h            |  273 +++++
 tools/testing/selftests/rseq/rseq-x86.h            |  306 ++++++
 tools/testing/selftests/rseq/rseq.c                |  231 ++++
 tools/testing/selftests/rseq/rseq.h                |  454 ++++++++
 37 files changed, 3562 insertions(+), 1 deletion(-)
 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-arm.h
 create mode 100644 tools/testing/selftests/rseq/rseq-ppc.h
 create mode 100644 tools/testing/selftests/rseq/rseq-x86.h
 create mode 100644 tools/testing/selftests/rseq/rseq.c
 create mode 100644 tools/testing/selftests/rseq/rseq.h

-- 
2.1.4

[toc] | [next] | [standalone]

#1466656 — [RFC PATCH v8 6/9] Restartable sequences: wire up x86 32/64 system call

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 <linux@arm.linux.org.uk>
CC: Catalin Marinas <catalin.marinas@arm.com>
CC: Will Deacon <will.deacon@arm.com>
CC: Thomas Gleixner <tglx@linutronix.de>
CC: Paul Turner <pjt@google.com>
CC: Andrew Hunter <ahh@google.com>
CC: Peter Zijlstra <peterz@infradead.org>
CC: Andy Lutomirski <luto@amacapital.net>
CC: Andi Kleen <andi@firstfloor.org>
CC: Dave Watson <davejwatson@fb.com>
CC: Chris Lameter <cl@linux.com>
CC: Ingo Molnar <mingo@redhat.com>
CC: "H. Peter Anvin" <hpa@zytor.com>
CC: Ben Maurer <bmaurer@fb.com>
CC: Steven Rostedt <rostedt@goodmis.org>
CC: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
CC: Josh Triplett <josh@joshtriplett.org>
CC: Linus Torvalds <torvalds@linux-foundation.org>
CC: Andrew Morton <akpm@linux-foundation.org>
CC: Boqun Feng <boqun.feng@gmail.com>
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(+)

diff --git a/arch/x86/entry/syscalls/syscall_32.tbl b/arch/x86/entry/syscalls/syscall_32.tbl
index f848572..9c3fb2b 100644
--- a/arch/x86/entry/syscalls/syscall_32.tbl
+++ b/arch/x86/entry/syscalls/syscall_32.tbl
@@ -386,3 +386,4 @@
 377	i386	copy_file_range		sys_copy_file_range
 378	i386	preadv2			sys_preadv2			compat_sys_preadv2
 379	i386	pwritev2		sys_pwritev2			compat_sys_pwritev2
+380	i386	rseq			sys_rseq
diff --git a/arch/x86/entry/syscalls/syscall_64.tbl b/arch/x86/entry/syscalls/syscall_64.tbl
index e9ce9c7..83f5ac8 100644
--- a/arch/x86/entry/syscalls/syscall_64.tbl
+++ b/arch/x86/entry/syscalls/syscall_64.tbl
@@ -335,6 +335,7 @@
 326	common	copy_file_range		sys_copy_file_range
 327	64	preadv2			sys_preadv2
 328	64	pwritev2		sys_pwritev2
+329	common	rseq			sys_rseq
 
 #
 # x32-specific system call numbers start at 512 to avoid cache impact
-- 
2.1.4

[toc] | [prev] | [next] | [standalone]

#1466659 — [RFC PATCH v8 2/9] tracing: instrument restartable sequences

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
CC: Thomas Gleixner <tglx@linutronix.de>
CC: Paul Turner <pjt@google.com>
CC: Andrew Hunter <ahh@google.com>
CC: Peter Zijlstra <peterz@infradead.org>
CC: Andy Lutomirski <luto@amacapital.net>
CC: Andi Kleen <andi@firstfloor.org>
CC: Dave Watson <davejwatson@fb.com>
CC: Chris Lameter <cl@linux.com>
CC: Ingo Molnar <mingo@redhat.com>
CC: "H. Peter Anvin" <hpa@zytor.com>
CC: Ben Maurer <bmaurer@fb.com>
CC: Steven Rostedt <rostedt@goodmis.org>
CC: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
CC: Josh Triplett <josh@joshtriplett.org>
CC: Linus Torvalds <torvalds@linux-foundation.org>
CC: Andrew Morton <akpm@linux-foundation.org>
CC: Russell King <linux@arm.linux.org.uk>
CC: Catalin Marinas <catalin.marinas@arm.com>
CC: Will Deacon <will.deacon@arm.com>
CC: Michael Kerrisk <mtk.manpages@gmail.com>
CC: Boqun Feng <boqun.feng@gmail.com>
CC: linux-api@vger.kernel.org
---
 include/trace/events/rseq.h | 64 +++++++++++++++++++++++++++++++++++++++++++++
 kernel/rseq.c               | 11 +++++++-
 2 files changed, 74 insertions(+), 1 deletion(-)
 create mode 100644 include/trace/events/rseq.h

diff --git a/include/trace/events/rseq.h b/include/trace/events/rseq.h
new file mode 100644
index 0000000..63a8eb7
--- /dev/null
+++ b/include/trace/events/rseq.h
@@ -0,0 +1,64 @@
+#undef TRACE_SYSTEM
+#define TRACE_SYSTEM rseq
+
+#if !defined(_TRACE_RSEQ_H) || defined(TRACE_HEADER_MULTI_READ)
+#define _TRACE_RSEQ_H
+
+#include <linux/tracepoint.h>
+#include <linux/types.h>
+
+TRACE_EVENT(rseq_update,
+
+	TP_PROTO(struct task_struct *t),
+
+	TP_ARGS(t),
+
+	TP_STRUCT__entry(
+		__field(s32, cpu_id)
+		__field(u32, event_counter)
+	),
+
+	TP_fast_assign(
+		__entry->cpu_id = raw_smp_processor_id();
+		__entry->event_counter = t->rseq_event_counter;
+	),
+
+	TP_printk("cpu_id=%d event_counter=%u",
+		__entry->cpu_id, __entry->event_counter)
+);
+
+TRACE_EVENT(rseq_ip_fixup,
+
+	TP_PROTO(void __user *regs_ip, void __user *start_ip,
+		void __user *post_commit_ip, void __user *abort_ip,
+		u32 kevcount, int ret),
+
+	TP_ARGS(regs_ip, start_ip, post_commit_ip, abort_ip, kevcount, ret),
+
+	TP_STRUCT__entry(
+		__field(void __user *, regs_ip)
+		__field(void __user *, start_ip)
+		__field(void __user *, post_commit_ip)
+		__field(void __user *, abort_ip)
+		__field(u32, kevcount)
+		__field(int, ret)
+	),
+
+	TP_fast_assign(
+		__entry->regs_ip = regs_ip;
+		__entry->start_ip = start_ip;
+		__entry->post_commit_ip = post_commit_ip;
+		__entry->abort_ip = abort_ip;
+		__entry->kevcount = kevcount;
+		__entry->ret = ret;
+	),
+
+	TP_printk("regs_ip=%p start_ip=%p post_commit_ip=%p abort_ip=%p kevcount=%u ret=%d",
+		__entry->regs_ip, __entry->start_ip, __entry->post_commit_ip,
+		__entry->abort_ip, __entry->kevcount, __entry->ret)
+);
+
+#endif /* _TRACE_SOCK_H */
+
+/* This part must be outside protection */
+#include <trace/define_trace.h>
diff --git a/kernel/rseq.c b/kernel/rseq.c
index 32bc1d2..a102fcc 100644
--- a/kernel/rseq.c
+++ b/kernel/rseq.c
@@ -32,6 +32,9 @@
 #include <linux/types.h>
 #include <asm/ptrace.h>
 
+#define CREATE_TRACE_POINTS
+#include <trace/events/rseq.h>
+
 /*
  * The restartable sequences mechanism is the overlap of two distinct
  * restart mechanisms: a sequence counter tracking preemption and signal
@@ -137,6 +140,7 @@ static bool rseq_update_cpu_id_event_counter(struct task_struct *t)
 	u.e.event_counter = ++t->rseq_event_counter;
 	if (__put_user(u.v, &t->rseq->u.v))
 		return false;
+	trace_rseq_update(t);
 	return true;
 }
 
@@ -168,8 +172,13 @@ static bool rseq_ip_fixup(struct pt_regs *regs)
 	void __user *start_ip = NULL;
 	void __user *post_commit_ip = NULL;
 	void __user *abort_ip = NULL;
+	bool ret;
 
-	if (!rseq_get_rseq_cs(t, &start_ip, &post_commit_ip, &abort_ip))
+	ret = rseq_get_rseq_cs(t, &start_ip, &post_commit_ip, &abort_ip);
+	trace_rseq_ip_fixup((void __user *)instruction_pointer(regs),
+		start_ip, post_commit_ip, abort_ip, t->rseq_event_counter,
+		ret);
+	if (!ret)
 		return false;
 
 	/* Handle potentially not being within a critical section. */
-- 
2.1.4

[toc] | [prev] | [next] | [standalone]

#1466661 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

On Fri, Aug 19, 2016 at 1:07 PM, Mathieu Desnoyers
<mathieu.desnoyers@efficios.com> wrote:
>
> Benchmarking various approaches for reading the current CPU number:

So I'd like to see the benchmarks of something that actually *does* something.

IOW, what's the bigger-picture "this is what it actually is useful
for, and how it speeds things up".

Nobody gets a cpu number just to get a cpu number - it's not a useful
thing to benchmark. What does getcpu() so much that we care?

We've had tons of clever features that nobody actually uses, because
they aren't really portable enough. I'd like to be convinced that this
is actually going to be used by real applications.

                 Linus

[toc] | [prev] | [next] | [standalone]

#1466674 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

> Nobody gets a cpu number just to get a cpu number - it's not a useful
> thing to benchmark. What does getcpu() so much that we care?

malloc is the primary target I believe. Saves lots of memory to keep
caches per CPU rather than per thread.

-Andi

[toc] | [prev] | [next] | [standalone]

#1466687 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

On Fri, Aug 19, 2016 at 01:56:11PM -0700, Andi Kleen wrote:
> > Nobody gets a cpu number just to get a cpu number - it's not a useful
> > thing to benchmark. What does getcpu() so much that we care?
> 
> malloc is the primary target I believe. Saves lots of memory to keep
> caches per CPU rather than per thread.

Agreed, a competent default malloc() in glibc would be a very nice change
from the current state.

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1466696 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

On Fri, Aug 19, 2016 at 2:19 PM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> On Fri, Aug 19, 2016 at 01:56:11PM -0700, Andi Kleen wrote:
>>
>> malloc is the primary target I believe. Saves lots of memory to keep
>> caches per CPU rather than per thread.
>
> Agreed, a competent default malloc() in glibc would be a very nice change
> from the current state.

I agree that malloc can be a very good target for something like this,
but it is also something that is quite complicated. A general-purpose
allocator that could be used by glibc and has not just the performance
but the debug stuff etc that people inevitably want is a big project.
And then the people who have special needs end up writing their own
allocators anyway, just because they care about certain layout and
access patterns...

Put another way: I'd really like to see some real numbers and use,
rather than "this can be used for.."

             Linus

[toc] | [prev] | [next] | [standalone]

#1466725 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

On Fri, Aug 19, 2016 at 02:32:13PM -0700, Linus Torvalds wrote:
> On Fri, Aug 19, 2016 at 2:19 PM, Paul E. McKenney
> <paulmck@linux.vnet.ibm.com> wrote:
> > On Fri, Aug 19, 2016 at 01:56:11PM -0700, Andi Kleen wrote:
> >>
> >> malloc is the primary target I believe. Saves lots of memory to keep
> >> caches per CPU rather than per thread.
> >
> > Agreed, a competent default malloc() in glibc would be a very nice change
> > from the current state.
> 
> I agree that malloc can be a very good target for something like this,
> but it is also something that is quite complicated. A general-purpose
> allocator that could be used by glibc and has not just the performance
> but the debug stuff etc that people inevitably want is a big project.
> And then the people who have special needs end up writing their own
> allocators anyway, just because they care about certain layout and
> access patterns...
> 
> Put another way: I'd really like to see some real numbers and use,
> rather than "this can be used for.."

No argument here!

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1466692 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

On Fri, Aug 19, 2016 at 01:56:11PM -0700, Andi Kleen wrote:
> > Nobody gets a cpu number just to get a cpu number - it's not a useful
> > thing to benchmark. What does getcpu() so much that we care?
> 
> malloc is the primary target I believe. Saves lots of memory to keep
> caches per CPU rather than per thread.

Also improves locality; that does seem like a good idea.  Has anyone
written and tested the corresponding changes to a malloc implementation?

- Josh Triplett

[toc] | [prev] | [next] | [standalone]

#1466680 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

On Fri, Aug 19, 2016 at 01:23:57PM -0700, Linus Torvalds wrote:
> On Fri, Aug 19, 2016 at 1:07 PM, Mathieu Desnoyers
> <mathieu.desnoyers@efficios.com> wrote:
> >
> > Benchmarking various approaches for reading the current CPU number:
> 
> So I'd like to see the benchmarks of something that actually *does* something.
> 
> IOW, what's the bigger-picture "this is what it actually is useful
> for, and how it speeds things up".
> 
> Nobody gets a cpu number just to get a cpu number - it's not a useful
> thing to benchmark. What does getcpu() so much that we care?

The combination of CPU number and restartable sequence allows userspace
to write "per-CPU" rather than "per-thread" algorithms, just as the
kernel can.  The kernel can do that with preempt_disable().  Userspace
can do it with "tell me my CPU and restart me if preempted".

But yes, this needs a benchmark of, for instance, urcu implemented on
top of this, or some concrete data structure.

[toc] | [prev] | [next] | [standalone]

#1466686 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

On Fri, Aug 19, 2016 at 1:44 PM, Josh Triplett <josh@joshtriplett.org> wrote:
>
> The combination of CPU number and restartable sequence allows userspace
> to write "per-CPU" rather than "per-thread" algorithms, just as the
> kernel can.  The kernel can do that with preempt_disable().  Userspace
> can do it with "tell me my CPU and restart me if preempted".

Yes, I understand what the patch series wants to do. But there hasn't
been a lot of discussion about why per-cpu would be better than
per-thread, or who would actually use this.

The kernel cares about per-cpu, because as far as the kernel is
concerned, that largely _is_ threading inside the kernel.

I'd feel a lot more warm and fuzzy about this all if I'd also see what
the usage scenario is, and then the numbers on top of that.

We really _have_ had too many clever interfaces that basically never
saw any real use, because the application writers don't want to limit
themselves to just Linux, and even if they are happy to do that, they
don't want to then limit themselves to a fairly modern kernel, and
they don't want to have two different code bases.

For example, there's been a talk about number of instructions and
cycles on ARMv7, but it's not clear whether the use case is going to
care about tens of cycles of overhead much less individual instruction
counts. Those instruction counts may matter when you benchmark an
individual "cpu-atomic add", but may not matter when you actually
benchmark something much bigger.

And if people end up waiting for kernel support to be universally
available, then ARMv7 isn't even all that relevant any more. It takes
years for things like this to percolate out. In the android space, you
get new hardware quicker than you get new software..

           Linus

[toc] | [prev] | [next] | [standalone]

#1470285 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

----- On Aug 19, 2016, at 4:23 PM, Linus Torvalds torvalds@linux-foundation.org wrote:

> On Fri, Aug 19, 2016 at 1:07 PM, Mathieu Desnoyers
> <mathieu.desnoyers@efficios.com> wrote:
>>
>> Benchmarking various approaches for reading the current CPU number:
> 
> So I'd like to see the benchmarks of something that actually *does* something.
> 
> IOW, what's the bigger-picture "this is what it actually is useful
> for, and how it speeds things up".
> 
> Nobody gets a cpu number just to get a cpu number - it's not a useful
> thing to benchmark. What does getcpu() so much that we care?
> 
> We've had tons of clever features that nobody actually uses, because
> they aren't really portable enough. I'd like to be convinced that this
> is actually going to be used by real applications.

I completely agree with your request for real-life application numbers.

The most appealing application we have so far is Dave Watson's Facebook
services using jemalloc as a memory allocator. It would be nice if he
could re-run those benchmarks with my rseq implementation. The trade-offs
here are about speed and memory usage:

1) single process-wide pool:
   - speed: does not scale well to many-cores,
   + efficient use of memory.
2) per-thread pools:
   + speed: scales really well to many-cores,
   - inefficient use of memory.
3) per-cpu pools without rseq:
   - speed: requires atomic instructions due to migration and preemption,
   + efficient use of memory.
4) per-cpu pools with rseq:
   + speed: no atomic instructions required,
   + efficient use of memory.

His benchmarks should confirm that we get best of speed and
memory use with (4).

I plan to personally start working on integrating rseq with
the lttng-ust user-space tracer per-CPU ring buffer, but
I expect to mainly publish microbenchmarks, as most of
our heavy tracing users are proprietary applications, for
which it's tricky to publish numbers. I suspect that
microbenchmarks are not what you are looking for here.

Boqun Feng expressed interested in working on a
userspace RCU flavor that would implement per-CPU
(rather than per-thread) grace period tracking. I suspect
this will be a rather large undertaking. The benefits
should be visible as grace period overhead and speed
in applications that have many more threads than cores.

Paul Turner from Google probably have interesting numbers too,
but I suspect he is busy on other projects at the moment.

Let's see if we can get Dave Watson to provide those numbers.

Thanks!

Mathieu

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

[toc] | [prev] | [next] | [standalone]

#1470309 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

On 8/25/16, 10:08 AM, "Mathieu Desnoyers" <mathieu.desnoyers@efficios.com> wrote:
> The most appealing application we have so far is Dave Watson's Facebook
>    services using jemalloc as a memory allocator. It would be nice if he
>    could re-run those benchmarks with my rseq implementation. The trade-offs
>    here are about speed and memory usage:
 
One piece of context I’d like to provide about our investigation into using rseq for malloc – I think that it’s really important to keep in mind that we’ve optimized the software that we write to survive well in a world where there’s a high memory cost for jemalloc for each thread and jemalloc is unable to have allocation caches as large as we would like. We’re not going to have real world benchmarks that show a magical improvement with rseq because over time we’ve baked the constraints of our environment into the design of our programs and optimized for the current set of APIs the kernel provides. I do think rseq provides a benefit even for applications optimized for today’s malloc implementations. But the real benefit is the new types of application designed that rseq enables and the ability for rseq to provide predictable performance for low-level APIs with much less investment from users. I’ll illustrate the costs that rseq would let us avoid with two examples of design choices we’ve made:

1) Because jemalloc uses a per-thread cache, threads that are sleeping have a high memory cost. For example, if you have a thread-pool with 100 threads but only 10 are used most of the time the other 90 threads will still have a dormant cache consuming memory. In order to combat this we have an abstraction called MemoryIdler (https://github.com/facebook/folly/blob/master/folly/detail/MemoryIdler.h) which is essentially a wrapper around futex that signals jemalloc to release its caches when the thread is idle. From what I can tell this is a practice that isn’t widely adopted even though it can save a substantial amount of memory – rseq makes this a moot point since caches can be per-cpu and the memory allocator does not need to worry about an idle thread hogging the cache.
2) The per-thread nature of malloc implementations has generally led people to avoid thread-per-request designs. Things like MemoryIdler can help you if a thread is going to be idle for seconds before it is used again, but if your thread makes a 100 ms RPC to another server clearing the cache is far too expensive to justify. But you still have a bunch of memory sitting around unused for 100ms. Multiply that by many concurrent requests and you are consuming a lot of memory. This has forced people to handle multiple requests in a single thread – this leads to problems of its own like a contested lock in one request impacting many other requests on the same thread. 

rseq opens up a whole world of algorithms to userspace – algorithms that are O(num CPUs) and where one can have an extremely fast fastpath at the cost of a slower slow path. Many of these algorithms are in use in the kernel today – per-cpu allocators, RCU, light-weight reader writer locks, etc. Even in cases where these APIs can be implemented today, a rseq implementation is often superior in terms of predictability and usability (eg per-thread counters consume more memory and are more expensive to read than per-cpu counters).

Isn’t the large number of uses of rseq-like algorithms in the kernel a pretty substantial sign that there would be demand for similar algorithms by user-space systems programmers?

-b

[toc] | [prev] | [next] | [standalone]

#1471099 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

On Thu, Aug 25, 2016 at 05:56:25PM +0000, Ben Maurer wrote:
> rseq opens up a whole world of algorithms to userspace – algorithms
> that are O(num CPUs) and where one can have an extremely fast fastpath
> at the cost of a slower slow path. Many of these algorithms are in use
> in the kernel today – per-cpu allocators, RCU, light-weight reader
> writer locks, etc. Even in cases where these APIs can be implemented
> today, a rseq implementation is often superior in terms of
> predictability and usability (eg per-thread counters consume more
> memory and are more expensive to read than per-cpu counters).
>
> Isn’t the large number of uses of rseq-like algorithms in the kernel a
> pretty substantial sign that there would be demand for similar
> algorithms by user-space systems programmers?

Yes and no.  It provides a substantial sign that such algorithms could
and should exist; however "someone should do this" doesn't demonstrate
that someone *will*.  I do think we need a concrete example of a
userspace user with benchmark numbers that demonstrate the value of this
approach.

Mathieu, do you have a version of URCU that can use rseq to work per-CPU
rather than per-thread?  URCU's data structures would work as a
benchmark.

Ben, Mathieu, Dave, do you have jemalloc benchmark numbers with and
without rseq?  (As well as memory usage numbers for the reduced memory
usage of per-CPU pools rather than per-thread pools?)

[toc] | [prev] | [next] | [standalone]

#1471909 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

----- On Aug 27, 2016, at 12:22 AM, Josh Triplett josh@joshtriplett.org wrote:

> On Thu, Aug 25, 2016 at 05:56:25PM +0000, Ben Maurer wrote:
>> rseq opens up a whole world of algorithms to userspace – algorithms
>> that are O(num CPUs) and where one can have an extremely fast fastpath
>> at the cost of a slower slow path. Many of these algorithms are in use
>> in the kernel today – per-cpu allocators, RCU, light-weight reader
>> writer locks, etc. Even in cases where these APIs can be implemented
>> today, a rseq implementation is often superior in terms of
>> predictability and usability (eg per-thread counters consume more
>> memory and are more expensive to read than per-cpu counters).
>>
>> Isn’t the large number of uses of rseq-like algorithms in the kernel a
>> pretty substantial sign that there would be demand for similar
>> algorithms by user-space systems programmers?
> 
> Yes and no.  It provides a substantial sign that such algorithms could
> and should exist; however "someone should do this" doesn't demonstrate
> that someone *will*.  I do think we need a concrete example of a
> userspace user with benchmark numbers that demonstrate the value of this
> approach.
> 
> Mathieu, do you have a version of URCU that can use rseq to work per-CPU
> rather than per-thread?  URCU's data structures would work as a
> benchmark.

I currently don't have a per-cpu flavor of liburcu. All the flavors are
per-thread, because currently the alternative requires atomic operations
on the fast-path. We could indeed re-implement something similar to SRCU
(although under LGPLv2.1 license). I've looked at what would be required
over the weekend, and it seems feasible, but in the short term my customers
expect me to focus my work on speeding up the LTTng-UST tracer per-cpu
ring buffer by adapting it to rseq. Completing the liburcu per-cpu flavor
will be in my spare time for now.

I expect liburcu per-cpu flavor to improve the slow path in many-threads
use-cases (smaller grace period overhead), but not the fast path much,
except perhaps by allowing faster memory reclaim in update-heavy workloads,
which could then lead to better use of the cache even for reads.

> 
> Ben, Mathieu, Dave, do you have jemalloc benchmark numbers with and
> without rseq?  (As well as memory usage numbers for the reduced memory
> usage of per-CPU pools rather than per-thread pools?)

Before I started reimplementing rseq, the numbers presented by Facebook
at https://lkml.org/lkml/2015/10/22/588 were in my opinion a good proof
that rseq is useful. I'm not sure if their memoryidler API was used back
then.

I could take Dave's jemalloc branch adapted to Paul Turner's rseq and
adapt it to mine. Then we could use this allocator to compare the
memory use and speed of heavily multi-threaded applications.

Thoughts ?

Thanks,

Mathieu

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

[toc] | [prev] | [next] | [standalone]

#1471964 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

On Mon, Aug 29, 2016 at 03:16:52PM +0000, Mathieu Desnoyers wrote:
> ----- On Aug 27, 2016, at 12:22 AM, Josh Triplett josh@joshtriplett.org wrote:
> > Ben, Mathieu, Dave, do you have jemalloc benchmark numbers with and
> > without rseq?  (As well as memory usage numbers for the reduced memory
> > usage of per-CPU pools rather than per-thread pools?)
> 
> Before I started reimplementing rseq, the numbers presented by Facebook
> at https://lkml.org/lkml/2015/10/22/588 were in my opinion a good proof
> that rseq is useful. I'm not sure if their memoryidler API was used back
> then.
> 
> I could take Dave's jemalloc branch adapted to Paul Turner's rseq and
> adapt it to mine. Then we could use this allocator to compare the
> memory use and speed of heavily multi-threaded applications.
> 
> Thoughts ?

That seems like it would provide a good concrete benchmark of this work,
and demonstrate the value of it.

[toc] | [prev] | [next] | [standalone]

#1472197 — Re: [RFC PATCH v8 1/9] Restartable sequences system call

[Multipart message — attachments visible in raw view] — view raw

On Mon, Aug 29, 2016 at 03:16:52PM +0000, Mathieu Desnoyers wrote:
> ----- On Aug 27, 2016, at 12:22 AM, Josh Triplett josh@joshtriplett.org wrote:
> 
> > On Thu, Aug 25, 2016 at 05:56:25PM +0000, Ben Maurer wrote:
> >> rseq opens up a whole world of algorithms to userspace – algorithms
> >> that are O(num CPUs) and where one can have an extremely fast fastpath
> >> at the cost of a slower slow path. Many of these algorithms are in use
> >> in the kernel today – per-cpu allocators, RCU, light-weight reader
> >> writer locks, etc. Even in cases where these APIs can be implemented
> >> today, a rseq implementation is often superior in terms of
> >> predictability and usability (eg per-thread counters consume more
> >> memory and are more expensive to read than per-cpu counters).
> >>
> >> Isn’t the large number of uses of rseq-like algorithms in the kernel a
> >> pretty substantial sign that there would be demand for similar
> >> algorithms by user-space systems programmers?
> > 
> > Yes and no.  It provides a substantial sign that such algorithms could
> > and should exist; however "someone should do this" doesn't demonstrate
> > that someone *will*.  I do think we need a concrete example of a
> > userspace user with benchmark numbers that demonstrate the value of this
> > approach.
> > 
> > Mathieu, do you have a version of URCU that can use rseq to work per-CPU
> > rather than per-thread?  URCU's data structures would work as a
> > benchmark.
> 
> I currently don't have a per-cpu flavor of liburcu. All the flavors are
> per-thread, because currently the alternative requires atomic operations
> on the fast-path. We could indeed re-implement something similar to SRCU
> (although under LGPLv2.1 license). I've looked at what would be required
> over the weekend, and it seems feasible, but in the short term my customers
> expect me to focus my work on speeding up the LTTng-UST tracer per-cpu
> ring buffer by adapting it to rseq. Completing the liburcu per-cpu flavor
> will be in my spare time for now.
> 

Just for you information.

I have been working on the new SRCU-like flavor of liburcu since last
week, but it took me a while to understand the directory architecture of
urcu...

I wrote only implemetion for rcu_read_{un}lock() and synchronize_rcu(),
and just is able to run the simplest multiflavor test case. My plan is
to post the code and some numbers(on x86 and ppc) by the end of this
week.

Regards,
Boqun

> I expect liburcu per-cpu flavor to improve the slow path in many-threads
> use-cases (smaller grace period overhead), but not the fast path much,
> except perhaps by allowing faster memory reclaim in update-heavy workloads,
> which could then lead to better use of the cache even for reads.
> 

[...]

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web