Linus Torvalds (torvalds.delete@this.linux-foundation.org) on August 21, 2018 2:34 pm wrote:
>
> I 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.

Actually, another thing worth mentioning is just "statistics".

It sounds ridiculously easy to do things like "count number of packets processed" or "count hash misses vs hits", but it turns out that in heavily threaded environments, doing things like operation statistics is sometimes some of the nastiest stuff there is.

It's trivial to do per-thread: just increment the counter in the per-thread area. Boom. Done. There are no races, because even on the worst kind of load-store machine you can just do

get thread pointer
load counter from memory off thread pointer
increment counter
store new counter off thread pointer

and you're done. No locks, no cache conflicts with other threads, no nothing.

The problem with the per-thread model is that it can be very expensive indeed to add all those per-thread statistics up. Thousands of threads is not even unusual. So maybe you can deal with some slop, and just have the threads periodically empoty their per-thread statistics into some cache-coherent pool or something.

It's solvable, don't get me wrong. But it has problems.

So you can solve it other ways. One way is to have the remote atomics, and just do the statistics update "somewhere else" and asynchronously. That's a lovely model in many ways, but it's not portable.

Or you can just do actual cache-coherent locked loads to a global counter. That works fine for most cases, but it gets to be a complete disaster for the really hot counters on big machines. You'll potentially spend more time doing the statistics than you spend on the work you did.

Or you can play games. You could reserve one register for a "percpu base" - the same way you already have a base pointer for the thread local area, and rely on the OS updating it, and if you have a locally atomic (ie not SMP) instruction to do a read-modify-write, you can just do a single instruction

increment statistics(%cpubase)

and you're fine. On x86 you could use a segment register for the percpu base, the same way you use a segment register for the thread-local storage, and you're done.

With the above you get great cache behavior, no cross-cpu migration at all, and much better scaling too - you can add up the statistics by just iterating over the number of CPU's. Sure, that might still be a reasonably big number on a studly machine, but it's a much better proposition than the per-thread case.

But the above already requires that OS support for per-cpu base updates as you move around, and it also requires that you do have that single-instruction read-modify-write. So in practice, you can't actually do it, because it is so unportable.

So this is the kind of thing rseq can help with. A single memory add to update statistics - it should be really trivial and easy, but it actually is anything but. It's complex enough that people don't even do it at all.

With rseq, you can do basically the above "portably" (you have to have rseq) with two normal reads and write instruciton. Regular reads and writes too, not some slow cache-atomic ones.

There's a trivial (again normal instrucvtion) sequence to start the critical section (to a magic location you had registered with the kernel earlier), one read of the percpu base value, one read of the actual counter value, and one write of the new counter value.

If you got scheduled away, you get aborted and restart the sequence (otr maybe you decide to fall back to cacheline atomic, that's probably the better model anyway)

That kind of silly low-level thing that sounds trivial - but really isn't - is what rseq is about. Things that sound so simple that you'd not even realize that they are hard to implement.

So per-cpu memory allocators, trace buffers, counters. Things that sound obvious and trivial, but are pretty basic and aren't trivial at all in user space, and where locking is much too expensive, and transactional memory doesn't even help.

Linus