Avoiding ping pong

By: Linus Torvalds (torvalds.delete@this.linux-foundation.org), December 10, 2014 10:56 am
Room: Moderated Discussions
Konrad Schwarz (no.spam.delete@this.no.spam) on December 10, 2014 6:23 am wrote:
>
> And this really clinches the argument: to use reference counts, you need acyclic (directed) graphs.

Note that for cyclic graphs, you'd still often use atomics, just not generally reference counts (or quite possibly in addition to reference counts - with the reference count being used to track usage separate from the internal graph usage).

Think of the usual trivial traversal model: walk the graph, do something to each entry, and set a flag that you've done it (exactly because of cycles). Now, think about what happens in threaded environments. Yeah, that "do something and set a flag" is suddenly very much racy.

And for exactly the same reason as for reference counts, using an external lock is problematic. So you tend to want to have lockless models - ie atomics. Instead of an atomic increment, it might be an atomic compare-and-exchange ("set state to 'in progress', but only if nobody else already did so).

(Combine with "use sequence number instead of simple flag", in order to avoid things like "have to do a second traversal just to clear the flag again to do the next round")

And to make things more interesting still, it's not usually a "one or the other" situation, it's often a combination of things. I already mentioned using reference counts in addition to that whole "have I handled this already" flag/sequence count. But you then generally have other models too, including straight traditional locking on a higher level (maybe you want to traverse the graph concurrently, but you do not want to have multiple different traversals active at the same time).

And you can do various other fancy tricks. In Linux, we introduced this notion of a "reflock" that is both a reference count and a lock, and has very specific semantic guarantees (reference counts can be incremented atomically without taking the lock, but only if nobody else holds the lock etc).

And yes, you can often hide this from the user. A garbage collector is obviously doing exactly that kind of graph traversal (and often uses sequence counts not just to avoid that dual traversal, but for more fundamental reasons: to avoid a certain class of races you may well want to delay actual freeing, and use the generational data of the sequence count to free things only after they haven't been reachable for two or more cycles).

Of course, once you get into more complex situations, you do end up often effectively wanting LL/SC rather than just a simple unconditional atomic RMW instruction. So I'm absolutely not against the LL/SC model, I just think that you do want both, and I think having ARM64 add atomic rmw operations is actually a good thing.

Linus
< Previous Post in ThreadNext Post in Thread >
TopicPosted ByDate
ARMv8 getting atomic operationsdmcq2014/12/02 04:32 PM
  ARMv8 getting atomic operationsMaynard Handley2014/12/02 06:33 PM
    ARMv8 getting atomic operationsDoug S2014/12/02 09:30 PM
      ARMv8 getting atomic operationsdmcq2014/12/03 02:16 AM
      ARMv8 getting atomic operationsMaynard Handley2014/12/03 08:20 AM
      ARMv8 getting atomic operationsBrett2014/12/03 03:46 PM
    ARMv8 getting atomic operationsAndreas2014/12/03 05:51 AM
      ARMv8 getting atomic operationsLinus Torvalds2014/12/03 10:15 AM
        ARMv8 getting atomic operationsanon2014/12/03 04:08 PM
          Guaranteed transactionsPaul A. Clayton2014/12/03 07:04 PM
            Guaranteed transactionsanon2014/12/03 07:38 PM
              Avoiding ping pongPaul A. Clayton2014/12/04 08:11 AM
                Avoiding ping ponganon2014/12/04 09:15 AM
                  OoO window is limitedPaul A. Clayton2014/12/04 12:06 PM
                Avoiding ping pongAaron Spink2014/12/04 11:01 AM
                  Avoiding ping pongKonrad Schwarz2014/12/04 12:10 PM
                    Avoiding ping pongAaron Spink2014/12/04 01:31 PM
                    Avoiding ping pongGabriele Svelto2014/12/04 01:49 PM
                      Avoiding ping pongKonrad Schwarz2014/12/04 10:08 PM
                        Avoiding ping pongGabriele Svelto2014/12/04 11:04 PM
                          Avoiding ping pongEric Bron nli2014/12/05 01:28 AM
                            Avoiding ping pongKonrad Schwarz2014/12/05 02:37 AM
                              Avoiding ping pongEric Bron nli2014/12/05 03:23 AM
                                Avoiding ping pongKlimax2014/12/05 04:47 AM
                                  Avoiding ping pongEric Bron2014/12/05 05:24 AM
                              Avoiding ping pongGabriele Svelto2014/12/05 09:38 AM
                                Avoiding ping pongKonrad Schwarz2014/12/07 01:28 PM
                                  Avoiding ping pongGabriele Svelto2014/12/08 06:10 PM
                                    Avoiding ping pongKonrad Schwarz2014/12/09 04:12 AM
                                      Avoiding ping pongGabriele Svelto2014/12/09 06:31 AM
                                        Avoiding ping ponganon2014/12/09 10:24 PM
                            Avoiding ping pongGabriele Svelto2014/12/05 09:17 AM
                              Avoiding ping pongEric Bron2014/12/05 09:32 AM
                                Avoiding ping pongGabriele Svelto2014/12/05 11:45 AM
                                  Avoiding ping pongEric Bron2014/12/06 01:20 AM
                                    Avoiding ping pongnksingh2014/12/06 02:42 AM
                                      Avoiding ping pongEric Bron2014/12/06 03:04 AM
                                        Avoiding ping pongGiGNiC2014/12/06 05:27 AM
                                          Avoiding ping pongEric Bron nli2014/12/06 05:44 AM
                                          Avoiding ping pongEric Bron2014/12/06 06:07 AM
                                            Avoiding ping pongnksingh2014/12/07 03:06 PM
                                              Avoiding ping pongEric Bron2014/12/08 03:17 AM
                                                Avoiding ping pongGiGNiC2014/12/08 10:53 AM
                                                Avoiding ping pongnksingh2014/12/08 04:53 PM
                                                  Avoiding ping pongEric Bron2014/12/09 12:33 AM
                                    Avoiding ping pongdmsc2014/12/06 03:12 AM
                                      Avoiding ping pongEric Bron2014/12/06 03:25 AM
                                        Avoiding ping pongKlimax2014/12/06 04:49 AM
                                          Avoiding ping pongrwessel2014/12/07 01:34 AM
                                        Avoiding ping pongdmsc2014/12/06 06:39 AM
                                        Avoiding ping pongKonrad Schwarz2014/12/07 01:37 PM
                                          Avoiding ping pongMichael S2014/12/07 03:37 PM
                                            Avoiding ping pongKonrad Schwarz2014/12/08 03:35 AM
                          Avoiding ping pongKonrad Schwarz2014/12/05 02:30 AM
                        Avoiding ping pongLinus Torvalds2014/12/05 11:58 AM
                          Avoiding ping pongEric Bron2014/12/06 01:42 AM
                            Avoiding ping pongnksingh2014/12/06 02:51 AM
                              Avoiding ping pongEric Bron2014/12/06 03:08 AM
                            Avoiding ping pongLinus Torvalds2014/12/06 12:25 PM
                              Avoiding ping pongnksingh2014/12/07 02:26 PM
                                Avoiding ping pongEric Bron2014/12/08 03:35 AM
                                  Avoiding ping pongBrett2014/12/08 09:00 AM
                                    Avoiding ping pongEric Bron2014/12/08 09:48 AM
                                    Avoiding ping pongrwessel2014/12/08 11:52 AM
                                      Avoiding ping pongBrett2014/12/08 12:58 PM
                                      Avoiding ping pongDoug S2014/12/08 01:04 PM
                              Avoiding ping pongJouni Osmala2014/12/08 01:45 AM
                                Avoiding ping ponganon2014/12/08 04:44 AM
                                  Avoiding ping pongJouni Osmala2014/12/08 12:10 PM
                                    Avoiding ping pongLinus Torvalds2014/12/08 12:34 PM
                                      Avoiding ping pongJouni Osmala2014/12/08 02:47 PM
                                        Avoiding ping pongLinus Torvalds2014/12/08 07:08 PM
                                          Avoiding ping pongGabriele Svelto2014/12/09 06:48 AM
                                            Avoiding ping pongMaynard Handley2014/12/09 10:41 AM
                                              Avoiding ping pongPatrick Chase2014/12/09 12:06 PM
                                              Avoiding ping pongGabriele Svelto2014/12/09 12:52 PM
                                                Avoiding ping pongPatrick Chase2014/12/09 01:08 PM
                                            Why read RWT or Reddit when you can get journalists to do it for you?Rob Thorpe2015/01/02 07:20 AM
                                              Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/02 10:21 AM
                                                Why read RWT or Reddit when you can get journalists to do it for you?EduardoS2015/01/02 10:37 AM
                                                  Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/03 11:00 AM
                                                Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron nli2015/01/02 01:28 PM
                                                  Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/03 11:02 AM
                                                    Why read RWT or Reddit when you can get journalists to do it for you?Michael S2015/01/03 11:36 AM
                                                      Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/03 12:11 PM
                                                        Why read RWT or Reddit when you can get journalists to do it for you?Michael S2015/01/03 12:30 PM
                                                          Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron2015/01/03 01:57 PM
                                                            KNL cacheDavid Kanter2015/01/03 06:36 PM
                                                              KNL cacheEric Bron2015/01/04 02:34 AM
                                                                KNL cacheMichael S2015/01/04 03:11 AM
                                                                  KNL cacheEric Bron2015/01/04 03:57 AM
                                                                    KNL cacheMichael S2015/01/04 04:21 AM
                                                                      KNL cacheEric Bron2015/01/04 04:58 AM
                                                          Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/07 04:47 AM
                                                            Why read RWT or Reddit when you can get journalists to do it for you?Michael S2015/01/07 07:27 AM
                                                              Manycores vs multicoresjuanrga2015/01/10 03:10 PM
                                                                Manycores vs multicoresAaron Spink2015/01/10 04:32 PM
                                                                  Manycores vs multicoresjuanrga2015/01/10 05:32 PM
                                                                    Manycores vs multicoresExophase2015/01/10 05:49 PM
                                                                      Manycores vs multicoresjuanrga2015/01/10 07:21 PM
                                                                        Manycores vs multicoresExophase2015/01/10 07:51 PM
                                                                        Manycores vs multicoresAaron Spink2015/01/10 08:03 PM
                                                                    Manycores vs multicoresAaron Spink2015/01/10 06:21 PM
                                                                      Manycores vs multicoresjuanrga2015/01/10 07:25 PM
                                                                        Manycores vs multicoresAaron Spink2015/01/10 08:11 PM
                                                                          Manycores vs multicoresJouni Osmala2015/01/11 03:50 AM
                                                                            Manycores vs multicoresjuanrga2015/01/11 07:58 AM
                                                                            Manycores vs multicorescoppice2015/01/12 09:01 PM
                                                                              Manycores vs multicoresJouni Osmala2015/01/13 03:38 AM
                                                                        Manycores vs multicoresanon2015/01/11 02:19 AM
                                                                      Manycores vs multicoresMichael S2015/01/11 04:44 AM
                                                                        Manycores vs multicoresAaron Spink2015/01/11 04:55 PM
                                                                          Manycores vs multicoresMichael S2015/01/12 03:41 AM
                                                                            Manycores vs multicoresEric Bron2015/01/12 05:29 AM
                                                                              Manycores vs multicoresEric Bron2015/01/12 05:30 AM
                                                        Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron2015/01/03 01:54 PM
                                                          Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/07 04:48 AM
                                                            Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron2015/01/07 06:41 AM
                                                              Manycores vs multicoresjuanrga2015/01/10 03:14 PM
                                                    Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron2015/01/03 01:42 PM
                                                      Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/07 05:03 AM
                                                        Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron2015/01/07 06:45 AM
                                                        Why read RWT or Reddit when you can get journalists to do it for you?Linus Torvalds2015/01/08 02:09 PM
                                                          Pink unicorns for salejuanrga2015/01/10 04:09 PM
                                                        Intentionally picking a competitors slow part is cheating ...Mark Roulo2015/01/08 05:37 PM
                                                          Intentionally picking a competitors slow part is cheating ...coppice2015/01/08 10:38 PM
                                                            Intentionally picking a competitors slow part is cheating ...Mark Roulo2015/01/09 08:13 AM
                                                              Intentionally picking a competitors slow part is cheating ...Anon2015/01/10 01:00 AM
                                                              Intentionally picking a competitors slow part is cheating ...David Hess2015/01/11 12:03 PM
                                                            Intentionally picking a competitors slow part is cheating ...someone2015/01/09 09:31 AM
                                                              Intentionally picking a competitors slow part is cheating ...coppice2015/01/12 08:45 PM
                                                                Intentionally picking a competitors slow part is cheating ...coppice2015/01/12 08:47 PM
                                                                  Intentionally picking a competitors slow part is cheating ...Michael S2015/01/13 06:53 AM
                                                                    Intentionally picking a competitors slow part is cheating ...coppice2015/01/13 08:44 AM
                                                                      Intentionally picking a competitors slow part is cheating ...Michael S2015/01/13 09:01 AM
                                                                        Intentionally picking a competitors slow part is cheating ...coppice2015/01/13 07:35 PM
                                                                      Core sizesjuanrga2015/01/13 11:28 AM
                                                          NVIDIA'S FIRST CPU IS A WINNER (Linley Gwennap)juanrga2015/01/10 03:34 PM
                                                        Why read RWT or Reddit when you can get journalists to do it for you?Patrick Chase2015/01/08 06:02 PM
                                                        Why read RWT or Reddit when you can get journalists to do it for you?coppice2015/01/08 09:18 PM
                                                          Why read RWT or Reddit when you can get journalists to do it for you?Patrick Chase2015/01/09 10:54 AM
                                                            Why read RWT or Reddit when you can get journalists to do it for you?Mark Roulo2015/01/09 11:59 AM
                                                              Why read RWT or Reddit when you can get journalists to do it for you?Patrick Chase2015/01/09 02:20 PM
                                                                Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron2015/01/09 02:30 PM
                                                            Alternatives to OOOE (again)juanrga2015/01/10 03:50 PM
                                                              Alternatives to OOOE (again)David Kanter2015/01/10 11:10 PM
                                                                Alternatives to OOOE (again)juanrga2015/01/11 07:30 AM
                                                            Why read RWT or Reddit when you can get journalists to do it for you?Gabriele Svelto2015/01/10 11:53 PM
                                              Why read RWT or Reddit when you can get journalists to do it for you?Fake Linus Torvalds2015/01/03 11:14 AM
                                                Why read RWT or Reddit when you can get journalists to do it for you?Rob Thorpe2015/01/03 07:25 PM
                                          Avoiding ping pongMaynard Handley2014/12/09 10:33 AM
                                            Avoiding ping pongPatrick Chase2014/12/09 12:54 PM
                                              Avoiding ping pongMaynard Handley2014/12/09 05:56 PM
                                      Avoiding ping pongSalvatore De Dominicis2014/12/09 07:51 AM
                                        Avoiding ping pongPatrick Chase2014/12/09 01:00 PM
                                      Avoiding ping pongook2014/12/11 02:31 AM
                                      Avoiding ping pongArt Scott2014/12/19 09:19 PM
                                        Avoiding ping pongEric Bron nli2014/12/20 03:05 AM
                                      What about specialization?Troll?2015/01/02 06:55 AM
                                        What about specialization?Ungo2015/01/04 02:27 PM
                                      Avoiding ping pongfewwef2015/01/05 07:16 PM
                                      Avoiding ping pongV.Krishn2015/01/08 05:11 AM
                                    Avoiding ping pongGabriele Svelto2014/12/08 06:32 PM
                                    Avoiding ping ponganon2014/12/08 10:37 PM
                            Avoiding ping pongKonrad Schwarz2014/12/10 05:23 AM
                              Avoiding ping pongLinus Torvalds2014/12/10 10:56 AM
                          Object reference lockingDavid W2014/12/08 10:36 PM
                            Object reference lockingPatrick Chase2014/12/09 03:52 PM
                              Object reference lockingDavid W2014/12/11 04:18 AM
                    ISA != interface for "most programmers"Paul A. Clayton2014/12/04 02:34 PM
                      ISA != interface for "most programmers"rwessel2014/12/04 06:50 PM
                  Interesting! (exporting hot lines/cache-aware ISA); "Please sir, I want some more" (NT)Paul A. Clayton2014/12/04 01:26 PM
                  Avoiding ping pongMichael S2014/12/06 02:48 PM
          ARMv8 getting atomic operationsLinus Torvalds2014/12/04 11:05 AM
            LL/SC idiom recognition is not admitting RMW superiorityPaul A. Clayton2014/12/04 01:34 PM
            ARMv8 getting atomic operationsanon2014/12/04 09:17 PM
    ARMv8 getting atomic operationsPatrick Chase2014/12/03 11:09 AM
  limited ordernksingh2014/12/04 09:17 PM
    I didn't understand this either. (NT)Konrad Schwarz2014/12/04 09:32 PM
    limited orderdmcq2014/12/05 01:13 AM
    limited orderbakaneko2014/12/05 08:11 AM
Reply to this Topic
Name:
Email:
Topic:
Body: No Text
How do you spell green?