Paul A. Clayton (paaronclayton.delete@this.gmail.com) on August 21, 2018 9:09 am wrote:
> Linus Torvalds (torvalds.delete@this.linux-foundation.org) on August 20, 2018 4:29 pm wrote:
> >
> > Linux now (merged into the latest released kernel version, 4.18) actually has
> > what could be seen as the reverse of that: "rseq" aka restartable sequences.
> >
> > It doesn't disable preemption (which is crazy and all kinds of stupid), but it does
> > allow user space to see if it has been preempted, and mark certain sequences to
> > be done atomically. And if preemption happens, the sequence gets aborted.
>
> Since threads have phases that benefit from not being significantly interrupted, I think there
> would be value to allowing a thread to express that a phase would extend beyond the normally
> allotted time slice

No.

People will just misuse that, and then you need a lot of BS code to prevent misuses etc.

Don't do it. There is no upside anyway.

> > So you can think of rseq as kind of like the OS equivalent of transactional memory, but instead
> > of the transactional sequence being aborted on a cache conflict, it gets aborted on preemption.
>
> Except that the abort happens after the preemption completes. If a thread gets
> a lock and starts work in a critical section, it cannot release the lock (and undo
> no longer appropriate work) when another thread is waiting on the lock.

That's stupid.

If you get a lock, you get a lock. End of story. You don't need any preemption protection.

No, rseq is very specifically for lockless things. Particularly things where you can do percpu work, and then "finalize" the work with a single store update.

Note that that does not mean that you can't do multiple stores. You'd do multiple stores to your own private copy, and then you do the actual lockless part with that atomic percpu "test everything and update".

And note that the "atomic" here is very much about the percpu "I'm not scheduled away" atomic sense. It's not about atomics in the "lock cacheline" sense (ie load-locked/store-conditional or the x86 "lock" prefix).

If you do locked operations, you're already doing things that are more expensive than rseq is designed for. Again, rseq is designed for per-cpu lockless algorithms. The main use case is literally a percpu memory allocator that doesn't need to take locks. There are others, but memory allocators can be so critical that you might as well see that as the primary one.

Maybe I shouldn't have compared it to TSX, because that migth have given you a false sense of what the intention is. rseq is literally about the "how do I avoid locking entirely, because locks are too expensive".

> (Some of the transactional memory proposals suggest NAKing conflicting remote
> requests or using versioned memory to give a transaction a larger window
> in which to complete, which is similar to extending the time slice.)

Yeah, and that's bullshit too, and causes deadlocks. It adds a *lot* of complexity exactly the same way that "allow timeslice extension" would add. It's a mistake. I know IBM supports that model, but nobody sane calls it simple, and it has a very nasty go-slow case.

Yeah, yeah, even the simple abort model for TSX is broken and the cost of a flushed transaction is way too high, making it hard to do any generic transactional memory use.

You actually want something simpler and more limited, so that you can give performance guarantees and avoid deadlocks.

Maybe you would be happier if I compared rseq to "a fancy compare-multiple-and-exchange". Something that can still fail, but where the critical section is really small so that you can guarantee forward progress without complexity.

> > And that, in turn, can be a big deal when you have 4 cores, but 4 million threads.
> > You don't want to have the memory overhead of per-thread allocations, when
> > all you really wanted was the cache advantages of per-cpu counters.
>
> Per-cpu or per "concurrent" thread?

It's a gray area. In practice, there is no difference.

In theory there might be, but since nobody cares.. Call it either.

> If hardware supported faster local atomics (which is problematic for x86 since the LOCK prefix is
> global in memory scope [and stronger than normal consistency]),

Atomics are expensive on pretty much any architecture.

x86 actually tends to be the best at them, despite the stronger memory model, so trying to make this about x86 is actually bad.

The best rseq speedup numbers actually came from 32-bit ARM, exactly because locking is much more expensive there and 32-bit ARM doesn't even have execution-safe atomics, and x86 does so well.

Note that on x86, you can do read-modify-write operations and it's atomic as long as you use a percpu area (so it's not atomic if other CPU's modify it, but it's atomic wrt interrupts or task switches etc). ARM64 added those too, but many architectures do not.

So your argument about memory consistency is pure and utter garbage. Weak memory consistency and the RISC model in general is actually worst for atomic performance, and you may have to have special "disable interrupts" just to get atomic behavior. x86, depending on what you do, can be a shining example and beacon of sanity.

> > It's a pretty limited use-case, and I don't expect normal users to really ever
> > see it. But it is designed to allow for things like per-cpu malloc libraries etc,
> > and a few other very specific situations where you can take advantage of it.
>
> (Normal application programmers presumably do not really ever
> see system calls but rather higher level abstractions.)

That's not even remotely true.

Things like read/write are very much normal app programmer interfaces. Pretty much all of POSIX is.

Once you get away from those standardized models, though, things change.

And rseq is not just way outside of POSIX, it's so low-level that you really wouldn't want to use it at an app level. So it's a low-level library thing, or perhaps a language abstraction that a compiler can use for per-cpu (as opposed to per-thread, which is easy) operations.

> I think transactional memory can be presented in a way that is useful enough and transparent/portable enough
> to have sufficiently significant

You get back to me when that is actually reality. Right now it's just a theory and not backed up by any kind of data what-so-ever.

As things are now, locking models actually perform better than transactional memory, with the strongest argument for transactional memory being "well, if your locks are bad, transactional memory can help you". So yeah, transactional memory can help for very specific locks that you have trouble making more fine-grained for whatever reason, but doesn't work for locking in general.

And entirely lockless ones perform better than either, but also quite limited.

rseq is about the lockless models, not about the locked ones.

But lockless programming is hard, and usually mainly useful inside some internal library implentation, or in some very special code that makes scalability a big deal (eg a kernel or a database).

Linus