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

Groups > linux.kernel > #1450241 > unrolled thread

Re: [RFC PATCH v7 1/7] Restartable sequences system call

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC PATCH v7 1/7] Restartable sequences system call Andy Lutomirski <luto@amacapital.net> - 2016-07-26 01:10 +0200
    Re: [RFC PATCH v7 1/7] Restartable sequences system call Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-07-26 05:10 +0200
      Re: [RFC PATCH v7 1/7] Restartable sequences system call Peter Zijlstra <peterz@infradead.org> - 2016-08-03 14:30 +0200
        Re: [RFC PATCH v7 1/7] Restartable sequences system call Andy Lutomirski <luto@amacapital.net> - 2016-08-03 18:50 +0200
          Re: [RFC PATCH v7 1/7] Restartable sequences system call Christoph Lameter <cl@linux.com> - 2016-08-03 20:40 +0200
            Re: [RFC PATCH v7 1/7] Restartable sequences system call Andy Lutomirski <luto@amacapital.net> - 2016-08-04 07:10 +0200
          Re: [RFC PATCH v7 1/7] Restartable sequences system call Boqun Feng <boqun.feng@gmail.com> - 2016-08-04 06:30 +0200
            Re: [RFC PATCH v7 1/7] Restartable sequences system call Andy Lutomirski <luto@amacapital.net> - 2016-08-04 07:20 +0200
              Re: [RFC PATCH v7 1/7] Restartable sequences system call Boqun Feng <boqun.feng@gmail.com> - 2016-08-09 18:20 +0200
                Re: [RFC PATCH v7 1/7] Restartable sequences system call Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-08-10 20:20 +0200
                Re: [RFC PATCH v7 1/7] Restartable sequences system call Andy Lutomirski <luto@amacapital.net> - 2016-08-10 21:10 +0200
                Re: [RFC PATCH v7 1/7] Restartable sequences system call Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-08-10 22:50 +0200
              Re: [RFC PATCH v7 1/7] Restartable sequences system call Andy Lutomirski <luto@amacapital.net> - 2016-08-10 21:40 +0200
      Re: [RFC PATCH v7 1/7] Restartable sequences system call Christoph Lameter <cl@linux.com> - 2016-08-03 20:40 +0200
        Re: [RFC PATCH v7 1/7] Restartable sequences system call Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-08-10 22:10 +0200
          Re: [RFC PATCH v7 1/7] Restartable sequences system call Christoph Lameter <cl@linux.com> - 2016-08-10 22:40 +0200

#1450241 — Re: [RFC PATCH v7 1/7] Restartable sequences system call

On Thu, Jul 21, 2016 at 2:14 PM, Mathieu Desnoyers
<mathieu.desnoyers@efficios.com> 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:

> diff --git a/kernel/rseq.c b/kernel/rseq.c
> new file mode 100644
> index 0000000..e1c847b
> --- /dev/null
> +++ b/kernel/rseq.c

> +/*
> + * 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

[toc] | [next] | [standalone]

#1450341

----- On Jul 25, 2016, at 7:02 PM, Andy Lutomirski luto@amacapital.net wrote:

> On Thu, Jul 21, 2016 at 2:14 PM, Mathieu Desnoyers
> <mathieu.desnoyers@efficios.com> 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.

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.

> 
>>
>>            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.


> 
>>
>>        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

> 
>>        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.

> 
>>
>>        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."

> 
>>
>>        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

> 
>>
>>        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.

> 
>>
>>        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)

> 
> Hmm, here are the docs, sort of:
> 
>> diff --git a/kernel/rseq.c b/kernel/rseq.c
>> new file mode 100644
>> index 0000000..e1c847b
>> --- /dev/null
>> +++ b/kernel/rseq.c
> 
>> +/*
>> + * 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"

> 
>> + *       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

> 
>> + *
>> + *       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.

> 
>> + *
>> + *   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


> 
> 
> --Andy

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

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

#1455783

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.

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

#1455893

On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> 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.
>

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.)

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

#1455952

On Wed, 3 Aug 2016, Andy Lutomirski wrote:

> > 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.

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

#1456166

On Aug 3, 2016 11:31 AM, "Christoph Lameter" <cl@linux.com> wrote:
>
> On Wed, 3 Aug 2016, Andy Lutomirski wrote:
>
> > > 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.

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

#1456148

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

On Wed, Aug 03, 2016 at 09:37:57AM -0700, Andy Lutomirski wrote:
> On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> > 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.
> >
> 
> 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.)

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

#1456171

On Wed, Aug 3, 2016 at 9:27 PM, Boqun Feng <boqun.feng@gmail.com> wrote:
> On Wed, Aug 03, 2016 at 09:37:57AM -0700, Andy Lutomirski wrote:
>> On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra <peterz@infradead.org> wrote:
>> > 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.
>> >
>>
>> 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
>

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.

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

#1458909

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

On Wed, Aug 03, 2016 at 10:03:32PM -0700, Andy Lutomirski wrote:
> On Wed, Aug 3, 2016 at 9:27 PM, Boqun Feng <boqun.feng@gmail.com> wrote:
> > On Wed, Aug 03, 2016 at 09:37:57AM -0700, Andy Lutomirski wrote:
> >> On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> >> > 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.
> >> >
> >>
> >> 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
> >
> 
> 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

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

#1459364

----- 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 <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.
> 
> 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


> 
> --Andy

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

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

#1459583

On Tue, Aug 9, 2016 at 9:13 AM, Boqun Feng <boqun.feng@gmail.com> wrote:
> On Wed, Aug 03, 2016 at 10:03:32PM -0700, Andy Lutomirski wrote:
>> On Wed, Aug 3, 2016 at 9:27 PM, Boqun Feng <boqun.feng@gmail.com> wrote:
>> > On Wed, Aug 03, 2016 at 09:37:57AM -0700, Andy Lutomirski wrote:
>> >> On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra <peterz@infradead.org> wrote:
>> >> > 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.
>> >> >
>> >>
>> >> 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
>> >
>>
>> 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

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

#1459888

----- 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

> 
> Regards,
> Boqun

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

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

#1459683

On Wed, Aug 3, 2016 at 10:03 PM, Andy Lutomirski <luto@amacapital.net> wrote:
> On Wed, Aug 3, 2016 at 9:27 PM, Boqun Feng <boqun.feng@gmail.com> wrote:
>> On Wed, Aug 03, 2016 at 09:37:57AM -0700, Andy Lutomirski wrote:
>>> On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra <peterz@infradead.org> wrote:
>>> > 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.
>>> >
>>>
>>> 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
>>
>
> 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

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

#1455950

On Tue, 26 Jul 2016, Mathieu Desnoyers wrote:

> > 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.

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

#1459760

----- On Aug 3, 2016, at 2:29 PM, Chris Lameter cl@linux.com wrote:

> On Tue, 26 Jul 2016, Mathieu Desnoyers wrote:
> 
>> > 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.

> 
>> 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

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

#1459877

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.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web