Fitting time slices to execution phases

By: Linus Torvalds (torvalds.delete@this.linux-foundation.org), August 21, 2018 2:34 pm
Room: Moderated Discussions
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
< Previous Post in ThreadNext Post in Thread >
TopicPosted ByDate
ARM turns to a god and a heroAM2018/08/16 09:32 AM
  ARM turns to a god and a heroMaynard Handley2018/08/16 09:41 AM
    ARM turns to a god and a heroDoug S2018/08/16 11:11 AM
    ARM turns to a god and a heroGeoff Langdale2018/08/16 11:59 PM
      ARM turns to a god and a herodmcq2018/08/17 05:12 AM
  ARM is somewhat misleadingAdrian2018/08/16 11:56 PM
    It's marketing materialGabriele Svelto2018/08/17 01:00 AM
      It's marketing materialMichael S2018/08/17 03:13 AM
        It's marketing materialdmcq2018/08/17 05:23 AM
          It's marketing materialAndrei Frumusanu2018/08/17 07:25 AM
        It's marketing materialLinus Torvalds2018/08/17 11:20 AM
          It's marketing materialGroo2018/08/17 01:44 PM
            It's marketing materialDoug S2018/08/17 02:14 PM
          promises and deliveriesAM2018/08/17 02:32 PM
            promises and deliveriesPassing Through2018/08/17 03:02 PM
              Just by way of clarification Passing Through2018/08/17 03:15 PM
                Just by way of clarification AM2018/08/18 12:49 PM
                  Just by way of clarification Passing Through2018/08/18 01:34 PM
                    This ain't the nineties any longerPassing Through2018/08/18 01:54 PM
                      This ain't the nineties any longerMaynard Handley2018/08/18 02:50 PM
                        This ain't the nineties any longerPassing Through2018/08/18 03:57 PM
                          This ain't the nineties any longerPassing Through2018/09/06 02:42 PM
                            This ain't the nineties any longerMaynard Handley2018/09/07 04:10 PM
                              This ain't the nineties any longerPassing Through2018/09/07 04:48 PM
                                This ain't the nineties any longerMaynard Handley2018/09/07 05:22 PM
                Just by way of clarification Wilco2018/08/18 01:26 PM
                  Just by way of clarification Passing Through2018/08/18 01:39 PM
                  Just by way of clarification none2018/08/18 10:52 PM
                    Just by way of clarification dmcq2018/08/19 08:32 AM
                      Just by way of clarification none2018/08/19 08:54 AM
                        Just by way of clarification dmcq2018/08/19 11:24 AM
                          Just by way of clarification none2018/08/19 11:52 AM
                  Just by way of clarification Gabriele Svelto2018/08/19 06:41 AM
                    Just by way of clarification Passing Through2018/08/19 09:25 AM
                      Whiteboards at Gatwick airport anyone? Passing Through2018/08/20 04:24 AM
          It's marketing materialMichael S2018/08/18 11:12 AM
          It's marketing materialBrett2018/08/18 05:22 PM
            It's marketing materialBrett2018/08/18 05:33 PM
              It's marketing materialAdrian2018/08/19 01:21 AM
        A76AM2018/08/17 02:45 PM
          A76Michael S2018/08/18 11:20 AM
            A76AM2018/08/18 12:39 PM
              A76Michael S2018/08/18 12:49 PM
                A76AM2018/08/18 01:06 PM
                  A76Doug S2018/08/18 01:43 PM
                    A76Maynard Handley2018/08/18 02:42 PM
                      A76Maynard Handley2018/08/18 04:22 PM
                        Why write zeros when one can use metadata?Paul A. Clayton2018/08/18 06:19 PM
                          Why write zeros when one can use metadata?Maynard Handley2018/08/19 11:12 AM
                            Dictionary compress might apply to memcopyPaul A. Clayton2018/08/19 01:45 PM
                        Instructions for zeroingKonrad Schwarz2018/08/30 06:37 AM
                          Instructions for zeroingMaynard Handley2018/08/30 08:41 AM
                          Instructions for zeroingAdrian2018/08/30 11:37 AM
                            dcbz -> dcbzl (was: Instructions for zeroing)hobold2018/08/31 01:50 AM
                              dcbz -> dcbzl (was: Instructions for zeroing)dmcq2018/09/01 05:28 AM
                      A76Travis2018/08/19 11:36 AM
                        A76Maynard Handley2018/08/19 12:22 PM
                          A76Travis2018/08/19 02:07 PM
                            A76Maynard Handley2018/08/19 06:24 PM
                        Remote atomicsmatthew2018/08/19 12:51 PM
                          Remote atomicsMichael S2018/08/19 01:58 PM
                            Remote atomicsmatthew2018/08/19 02:32 PM
                              Remote atomicsMichael S2018/08/19 02:36 PM
                                Remote atomicsmatthew2018/08/19 02:48 PM
                                  Remote atomicsMichael S2018/08/19 03:16 PM
                                    Remote atomicsRicardo B2018/08/20 10:05 AM
                            Remote atomicsdmcq2018/08/19 02:33 PM
                          Remote atomicsTravis2018/08/19 02:32 PM
                            Remote atomicsMichael S2018/08/19 02:46 PM
                              Remote atomicsTravis2018/08/19 05:35 PM
                                Remote atomicsMichael S2018/08/20 03:29 AM
                            Remote atomicsmatthew2018/08/19 07:58 PM
                              Remote atomicsanon2018/08/20 12:59 AM
                                Remote atomicsTravis2018/08/20 10:26 AM
                              Remote atomicsTravis2018/08/20 09:57 AM
                              Remote atomicsLinus Torvalds2018/08/20 04:29 PM
                                Fitting time slices to execution phasesPaul A. Clayton2018/08/21 09:09 AM
                                  Fitting time slices to execution phasesLinus Torvalds2018/08/21 02:34 PM
                                    Fitting time slices to execution phasesLinus Torvalds2018/08/21 03:31 PM
                                      Fitting time slices to execution phasesGabriele Svelto2018/08/21 03:54 PM
                                        Fitting time slices to execution phasesLinus Torvalds2018/08/21 04:26 PM
                                      Fitting time slices to execution phasesTravis2018/08/21 04:21 PM
                                        Fitting time slices to execution phasesLinus Torvalds2018/08/21 04:39 PM
                                          Fitting time slices to execution phasesTravis2018/08/21 04:59 PM
                                            Fitting time slices to execution phasesLinus Torvalds2018/08/21 05:13 PM
                                      Fitting time slices to execution phasesanon2018/08/21 04:27 PM
                                        Fitting time slices to execution phasesLinus Torvalds2018/08/21 06:02 PM
                                          Fitting time slices to execution phasesEtienne2018/08/22 02:28 AM
                                        Fitting time slices to execution phasesGabriele Svelto2018/08/22 03:07 PM
                                          Fitting time slices to execution phasesTravis2018/08/22 04:00 PM
                                          Fitting time slices to execution phasesanon2018/08/22 06:52 PM
                                    Fitting time slices to execution phasesTravis2018/08/21 04:37 PM
                                    Is preventing misuse that complex?Paul A. Clayton2018/08/23 05:42 AM
                                      Is preventing misuse that complex?Linus Torvalds2018/08/23 12:46 PM
                                        Is preventing misuse that complex?Travis2018/08/23 01:29 PM
                                          Is preventing misuse that complex?Travis2018/08/23 01:33 PM
                                            Is preventing misuse that complex?Jeff S.2018/08/24 07:57 AM
                                              Is preventing misuse that complex?Travis2018/08/24 08:47 AM
                                          Is preventing misuse that complex?Linus Torvalds2018/08/23 02:30 PM
                                            Is preventing misuse that complex?Travis2018/08/23 03:11 PM
                                              Is preventing misuse that complex?Linus Torvalds2018/08/24 01:00 PM
                                                Is preventing misuse that complex?Gabriele Svelto2018/08/24 01:25 PM
                                                  Is preventing misuse that complex?Linus Torvalds2018/08/24 01:33 PM
                                  Fitting time slices to execution phasesTravis2018/08/21 03:54 PM
                                rseq: holy grail rwlock?Travis2018/08/21 03:18 PM
                                  rseq: holy grail rwlock?Linus Torvalds2018/08/21 03:59 PM
                                    rseq: holy grail rwlock?Travis2018/08/21 04:27 PM
                                      rseq: holy grail rwlock?Linus Torvalds2018/08/21 05:10 PM
                                        rseq: holy grail rwlock?Travis2018/08/21 06:21 PM
                  ARM design housesMichael S2018/08/21 05:07 AM
                    ARM design housesWilco2018/08/22 12:38 PM
                      ARM design housesMichael S2018/08/22 02:21 PM
                        ARM design housesWilco2018/08/22 03:23 PM
                          ARM design housesMichael S2018/08/29 01:58 AM
                            Qualcomm's core naming scheme really, really sucksHeikki Kultala2018/08/29 02:19 AM
                A76Maynard Handley2018/08/18 02:07 PM
                  A76Michael S2018/08/18 02:32 PM
                    A76Maynard Handley2018/08/18 02:52 PM
                      A76Michael S2018/08/18 03:04 PM
    ARM is somewhat misleadingjuanrga2018/08/17 01:20 AM
    Surprised??Alberto2018/08/17 01:52 AM
      Surprised??Alberto2018/08/17 02:10 AM
      Surprised??none2018/08/17 02:46 AM
      Garbage talkAndrei Frumusanu2018/08/17 07:30 AM
        Garbage talkMichael S2018/08/17 07:43 AM
          Garbage talkAndrei Frumusanu2018/08/17 09:51 AM
            Garbage talkMichael S2018/08/18 11:29 AM
        Garbage talkAdrian2018/08/17 08:28 AM
          Garbage talkAlberto2018/08/17 09:20 AM
          Garbage talkAndrei Frumusanu2018/08/17 09:48 AM
            Garbage talkAdrian2018/08/17 10:17 AM
              Garbage talkAndrei Frumusanu2018/08/17 10:36 AM
                Garbage talkAdrian2018/08/17 02:53 PM
                  Garbage talkAndrei Frumusanu2018/08/18 12:17 AM
        More like a religion he?? ARM has an easy life :)Alberto2018/08/17 09:13 AM
          More like a religion he?? ARM has an easy life :)Andrei Frumusanu2018/08/17 09:34 AM
            More like a religion he?? ARM has an easy life :)Alberto2018/08/17 10:03 AM
              More like a religion he?? ARM has an easy life :)Andrei Frumusanu2018/08/17 10:43 AM
              More like a religion he?? ARM has an easy life :)Doug S2018/08/17 02:17 PM
              15W phone SoCsAM2018/08/17 03:04 PM
          More like a religion he?? ARM has an easy life :)Maynard Handley2018/08/17 12:29 PM
  my future stuff will be better than your old stuff, hey I'm a god at last (NT)Eric Bron2018/08/18 03:34 AM
    my future stuff will be better than your old stuff, hey I'm a god at lastnone2018/08/18 08:34 AM
Reply to this Topic
Name:
Email:
Topic:
Body: No Text
How do you spell avocado?