Re: [RFC PATCH v7 7/7] Restartable sequences: self-tests

On Fri, Aug 12, 2016 at 03:10:38AM +0000, Mathieu Desnoyers wrote:

----- On Aug 11, 2016, at 9:28 PM, Boqun Feng boqun.feng-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org wrote:

quoted

On Thu, Aug 11, 2016 at 11:26:30PM +0000, Mathieu Desnoyers wrote:

quoted

----- On Jul 24, 2016, at 2:01 PM, Dave Watson davejwatson-b10kYP2dOMg@public.gmane.org wrote:

quoted

quoted

quoted

+static inline __attribute__((always_inline))
+bool rseq_finish(struct rseq_lock *rlock,
+ intptr_t *p, intptr_t to_write,
+ struct rseq_state start_value)

quoted

quoted

This ABI looks like it will work fine for our use case. I don't think it
has been mentioned yet, but we may still need multiple asm blocks
for differing numbers of writes. For example, an array-based freelist push:

quoted

quoted

void push(void *obj) {
if (index < maxlen) {
freelist[index++] = obj;
}
}

quoted

quoted

would be more efficiently implemented with a two-write rseq_finish:

quoted

quoted

rseq_finish2(&freelist[index], obj, // first write
&index, index + 1, // second write
...);

quoted

Would pairing one rseq_start with two rseq_finish do the trick
there ?

Yes, two rseq_finish works, as long as the extra rseq management overhead
is not substantial.

I've added a commit implementing rseq_finish2() in my rseq volatile
dev branch. You can fetch it at:

https://github.com/compudj/linux-percpu-dev/tree/rseq-fallback

I also have a separate test and benchmark tree in addition to the
kernel selftests here:

https://github.com/compudj/rseq-test

I named the first write a "speculative" write, and the second write
the "final" write.

Maybe I miss something subtle, but if the first write is only a
"speculative" write, why can't we put it in the rseq critical section
rather than asm block? Like this:

do_rseq(..., result, targetptr, newval
	{
		newval = index;
		targetptr = &index;
		if (newval < maxlen)
			freelist[newval++] = obj;
		else
			result = false;
	}

No extra rseq_finish() is needed here, but maybe a little more
"speculative" writes?

This won't work unfortunately. The speculative stores need to be
between the rseq_event_counter comparison instruction in the rseq_finish
asm sequence and the final store. The ip fixup is really needed for
correctness of speculative stores. The sequence number scheme only works
for loads.

Putting it in the C code between rseq_start and rseq_finish would lead
to races such as:

thread A                                thread B
rseq_start
<preempted>
                                        <sched in>
                                        rseq_start
                                        freelist[offset + 1] = obj
                                        rseq_finish
                                           offset++
                                        <preempted>
<sched in>
freelist[newval + 1] = obj  <--- corrupts the list content.

Ah, right!

We couldn't do any "global"(real global or percpu) update in the rseq
critical section(code between rseq_start and rseq_finish), because
without an ip fixup, we cannot abort the critical section immediately,
we have to compare the event_counter in rseq_finish, but that's too late
for speculates stores.

<snip>

quoted

Besides, do we allow userspace programs do read-only access to the
memory objects modified by do_rseq(). If so, we have a problem when
there are two writes in a do_rseq()(either in the rseq critical section
or in the asm block), because in current implemetation, these two writes
are unordered, which makes the readers outside a do_rseq() could observe
the ordering of writes differently.

For rseq_finish2(), a simple solution would be making the "final" write
a RELEASE.

Indeed, we would need a release semantic for the final store here if this
is the common use. Or we could duplicate the "flavors" of rseq_finish2 and
add a rseq_finish2_release. We should find a way to eliminate code duplication

I'm in favor of a separate rseq_finish2_release().

there. I suspect we'll end up doing macros.

Me too. Lemme have a try ;-)

Regards,
Boqun

Thanks,

Mathieu

quoted

Regards,
Boqun

quoted

Thanks,

Mathieu

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

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