Avoiding ping pong

By: Linus Torvalds (torvalds.delete@this.linux-foundation.org), December 5, 2014 12:58 pm
Room: Moderated Discussions
Konrad Schwarz (no.spam.delete@this.no.spam) on December 4, 2014 11:08 pm wrote:
>
> Since it is being accessed in a multi-threaded way, via multiple access paths,
> generally it needs its own mutex -- otherwise, reference counting would not
> be required to be atomic and a lock of a higher-level object would suffice

The problem with reference counts is that you often need to take them *before* you take the lock that protects the object data.

The thing is, you have two different cases:

- object *reference*

- object data

and they have completely different locking.

Object data locking is generally per-object. Well, unless you don't have huge scalability issues, in which case you may have some external bigger lock (extreme case: one single global lock).

But object *referencing* is mostly about finding the object (and removing/freeing it). Is it on a hash chain? Is it in a tree? Linked list? When the reference count goes down to zero, it's not the object data that you need to protect (the object is not used by anything else, so there's nothing to protect!), it's the ways to find the object you need to protect.

And the lock for the lookup operation cannot be in the object, because - by definition - you don't know what the object is! You're trying to look it up, after all.

So generally you have a lock that protects the lookup operation some way, and the reference count needs to be atomic with respect to that lock.

And yes, that lock may well be sufficient, and now you're back to non-atomic reference counts. But you usually don't have just one way to look things up: you might have pointers from other objects (and that pointer is protected by the object locking of the other object), but there may be multiple such objects that point to this (which is why you have a reference count in the first place!).

See what happens? There is no longer one single lock for lookup. Imagine walking a graph of objects, where objects have pointers to each other. Each pointer implies a reference to an object, but as you walk the graph, you have to release the lock from the source object, so you have to take a new reference to the object you are now entering.

And in order to avoid deadlocks, you can not in the general case take the lock of the new object first - you have to release the lock on the source object, because otherwise (in a complex graph), how do you avoid simple ABBA deadlock?

So atomic reference counts fix that. They work because when you move from object A to object B, you can do this:

(a) you have a reference count to A, and you can lock A

(b) once object A is locked, the pointer from A to B is stable, and you know you have a reference to B (because of that pointer from A to B)

(c) but you cannot take the object lock for B (ABBA deadlock) while holding the lock on A

(d) increment the atomic reference count on B

(e) now you can drop the lock on A (you're "exiting" A)

(f) your reference count means that B cannot go away from under you despite unlocking A, so now you can lock B.

See? Atomic reference counts make this kind of situation possible. Yes, you want to avoid the overhead if at all possible (for example, maybe you have a strict ordering of objects, so you know you can walk from A to B, and never walk from B to A, so there is no ABBA deadlock, and you can just lock B while still holding the lock on A).

But if you don't have some kind of forced ordering, and if you have multiple ways to reach an object (and again - why have reference counts in the first place if that isn't true!) then atomic reference counts really are the simple and sane answer.

If you think atomic refcounts are unnecessary, that's a big flag that you don't actually understand the complexities of locking.

Trust me, concurrency is hard. There's a reason all the examples of "look how easy it is to parallellize things" tend to use simple arrays and don't ever have allocations or freeing of the objects.

People who think that the future is highly parallel are invariably completely unaware of just how hard concurrency really is. They've seen Linpack, they've seen all those wonderful examples of sorting an array in parallel, they've seen all these things that have absolutely no actual real complexity - and often very limited real usefulness.

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