Questions and comments about restartable sequences

[Torvald Riegel]

Hi Paul,

I have a few questions regarding restartable sequences, regarding
userspace.  I don't read LKML, so sorry if I missed something already
said elsewhere.  I'm doing concurrency stuff in glibc, so that's the
perspective of the following questions.  I'd like to see something like
the restartable sequences being offered, and would try to contribute to
the userspace side of this.

First, do you want to make the full sequence (e.g., including
preparatory work) speculative, or do you want to provide just a single
isntruction (eg, store) that is only conditionally executed?  The former
is, IOW, like a critical section that is executed but immediately
restarted once preemption occurs; the latter would restrict that to
predefined instruction sequences (eg, like the asm example in the
description of your v2 patch).
This affects how preparatory work can be done.  With just a
conditionally executed instruction, the preparatory work has to be
concurrent code because there can be interference by other threads that
is not noticed until the conditional instruction fails.  This means that
in C/C++, the program must use relaxed memory-order atomics so that the
compiler is aware that there is concurrency (e.g., so that it doesn't
reload a value from memory expecting it to still be the same because of
assuming sequential code by default).
With speculative execution of the sequence, the code and the compiler
are running sequentially until either commit or restart, so if
considering just this aspect, no atomics would be required.  However,
the compiler still needs to be aware of the restart (specifically, the
register allocator needs to be aware), and I believe would need compiler
support (or reuse any compiler support for transactional memory; there's
basically the same issue there).
The current condition of checking whether current rip is larger than
failure rip to see if one is still in the sequence seems to favor a
single conditionally executed instruction.  However, other conditions
might be possible (eg, let the MSB of the failure/restart rip be true if
no condition, immediately reset it after failure so that failure path is
clear, and just clear the MSB before attempting the commit to get a
nonambiguous state for the instruction after the commit).  If sticking
with the larger-than-failure-rip condition and still wanting to have
speculative execution of preparatory work, compiler support may be used
to inline all of it and put it before the commit in terms of addresses.
But that may be uglier than looking for a different scheme.

Second, TLS vs. gs/fs: I haven't read the prior discussion of this, but
you wrote that TLS would require per-thread initialization.  I believe
this could also be per-process initialization, for example if we reserve
a specific fixed TLS slot for it, as is already done for GCC's
transactional memory implementation.  Even without that, I suppose a
per-library-per-process initialization call should be sufficient because
TLS layout doesn't differ between threads?

Are spurious restarts possible (eg, to work around corner cases in the
implementation)?  If so, I think this should be called out in the
specification.  If not, I think this should be an explicit guarantee
too.

Thanks,

Torvald