Talk:ABA problem

Chart Needed

I just created this page with a basic description of the ABA problem. One thing I think could help readers is a graphic that demonstrates the processes and memory changing over time. Sutekh.destroyer (talk) 23:16, 18 February 2008 (UTC)

The briefcase example is overly dramatic and has unnecessary detail. Gvanrossum (talk) 22:56, 26 August 2011 (UTC)

The briefcase example is not actually describing the ABA problem or in a very abstract sense that goes beyond my understanding. If you want a name for it, you could call the problem that is described the AA' problem. Charlie's problem is that A' (the brief case filled with sand) is clearly not equal A (the brief case full of money), or alternatively that he and his his boss are using different notions of equalities. Charlie's problem is not that there was a B state in between. For comparison, Charlie would still have a problem, and this is the whole point of the story but not of the ABA problem, if Albert teleported the money out of the briefcase. — Preceding unsigned comment added by 84.226.131.225 (talk) 18:41, 21 November 2011 (UTC)

Misuse of volatile

Why declaring the top_ptr volatile ? —Preceding unsigned comment added by 82.67.122.43 (talk) 23:20, 17 October 2010 (UTC)

I assume it was introduced by a Java programmer who incorrectly believes that volatile has the same semantics in C++. I'll correct it. -98.186.176.38 (talk) 23:21, 1 June 2013 (UTC)

Use-after-free bug in example

The current version of the article contains this source code in an example:

  /* Naive lock-free stack which suffers from ABA problem.*/
  class Stack {
    std::atomic<Obj*> top_ptr;
    //
    // Pops the top object and returns a pointer to it.
    //
    Obj* Pop() {
      while(1) {
        Obj* ret_ptr = top_ptr;
        if (!ret_ptr) return 0;
        // For simplicity, suppose that we can ensure that this dereference is safe
        // (i.e., that no other thread has popped the stack in the meantime).
        Obj* next_ptr = ret_ptr->next;
        // If the top node is still ret, then assume no one has changed the stack.
        // (That statement is not always true because of the ABA problem)
        // Atomically replace top with next.
        if (top_ptr.compare_exchange_weak(ret_ptr, next_ptr)) {
          return ret_ptr;
        }
        // The stack has changed, start over.
      }
    }
    //
    // Pushes the object specified by obj_ptr to stack.
    //
    void Push(Obj* obj_ptr) {
      while(1) {
        Obj* next_ptr = top_ptr;
        obj_ptr->next = next_ptr;
        // If the top node is still next, then assume no one has changed the stack.
        // (That statement is not always true because of the ABA problem)
        // Atomically replace top with obj.
        if (top_ptr.compare_exchange_weak(next_ptr, obj_ptr)) {
          return;
        }
        // The stack has changed, start over.
      }
    }
  };

I just added the comment that starts "For simplicity,...". I'd like to demonstrate here that this is really a bug, though, in case anyone's unconvinced.

Suppose we have a stack top → A → B → C, and two threads that both want to execute this code:

    Obj* old_top = myStack.pop();
    std::cout << *old_top;
    delete old_top;

The first thread executes ret_ptr = top_ptr; we have its ret_ptr → A. Then the second thread does the same thing. Then the first thread runs to completion: it successfully pops A, prints it to cout, and deletes it. Then the second thread attempts to set next_ptr = ret_ptr->next... and accesses deallocated memory, and crashes!

Properly solving this bug is super hard ([1]), so I recommend that this article not attempt to solve it. Let's just document the problem in a comment and move on with the stuff that's relevant to the topic at hand. --Quuxplusone (talk) 23:13, 21 June 2013 (UTC)

real-life scenario

In my humble opinion the given "real-life scenario" is not a correct example. The problem is that real-life objects would be objects somewhere in the memory. It is very easy to compare states to be equal (usually by using the ==-operator). In Java you would just check it like that: if(mySuitcase != currentSuitcase) throw SecurityBreachException("Suitcase was stolen!!! release the hounds!!!");

ABA is about states. And states don't change. A suitcase isn't even a state, it *has* states (i.e. the content).

I try to make a better example:

Natalie is waiting in her green car at the red traffic light. She gets distracted when she sees man in a gorilla suit (Gary) approaching another man (Charlie) who is sitting in an airport terminal with a briefcase containing a large sum of money on the floor next to his feet. He is transporting it for his boss, so he does not know the suitcase's combination. While Gary is distracting Charlie (and Natalie), his partner-in-crime (Albert) decides to seize the opportunity to grab the money. He realizes that if Charlie turns his head and sees that his briefcase has disappeared, he will sound an alarm; after that, it is not likely that he and Gary will make it out of the airport without being stopped by security. Natalie is so distracted that she does not react to the honking from behind her. Albert quickly takes Charlie's briefcase and replaces it with an identical briefcase filled with sand to match the weight of the money. Gary finishes up his conversation with Charlie, he gets up, gets on the plane, and leaves. He is completely unaware that the briefcase now contains only sand. He should have just checked the ISN (International Suitcase Number). When Charlie's boss finally opens the briefcase, it is likely Charlie will be in a lot of trouble. Natalie now begins to wonder what the honking was all about. She looks at the traffic light, which is still glowing in the same red as before. The other motorists know that the lights switched from red to green and then again to red.

Mismatch between example and workaround

The recent edit to the example to simplify it has left the workaround section incongruously referring to 'Charlie and his briefcase', which no longer exists in the example. Either the edit example should be reverted, or the workaround amended--the current situation is very confusing! 144.32.48.65 (talk) 13:40, 26 January 2015 (UTC)

Gratuitous Examples

The examples listed are gratuitous, needlessly complicated, and distract from the issue at hand The ABA problem is simple and does not need a cast of characters and a secret mission to describe. Nor does such an example belong in an encyclopædic article, especially if it's inaccurate (see previous discussions). I suggest that the Charlie example be nixed, along with the relevant paragraph of the Workarounds section, which contributes nothing. Crimsoncere (talk) 11:03, 11 April 2015 (UTC)

"It's worse than that, he's dead Jim". The entire article like almost all in the Wiki makes the subject completely incomprehensible to anyone except someone who already understands it fully. 95.91.244.69 (talk) 15:17, 11 September 2016 (UTC)

This article is also completely out of touch with the practice of ABA-resistant software engineering. The idea of a 60 bit tag to safeguard against a thread being deprioritized between a couple CPU opcodes for 10 years is so pedantic it could almost be taken as a joke. The truth is people use the top 16 bits of a pointer for ABA. You can also use the ROL/ROR instructions to claim some of the lower bits too. For example, every pointer returned by malloc has 3 more bits you can use at the bottom. This is the sort of thing the article should mention. It's especially important now that PML5T x86-64 machines are becoming a thing. Those 16-bits at the top of the pointer just got reduced to 8-bits. There needs to be some kind of better, probability based explanation to how likely ABA issues are, based on the number of bits you have. Jartine (talk) 08:00, 27 August 2024 (UTC)

bad references

"Valois" occurs in square brackets as if it were a reference, but no expansion appears.

Two entries for papers by Dechev et al. appear under "references" but are not referenced in the article.

DHR (talk) 19:44, 22 December 2015 (UTC)

Why does it have to be John? What's wrong with Natalie?

176.183.5.133 changed Natalie to John without adding anything by that. I don't see how the sex/gender would be relevant, so why change it? — Preceding unsigned comment added by 212.147.26.17 (talk) 09:11, 27 June 2017 (UTC)

174.47.210.5 (talk) 19:11, 17 August 2017 (UTC)== Example still does not seem accurate ==

An important part of the ABA problem seems to be that the B process alters the shared memory after preempting A. This does not carry over to the example, unless the children are secretly altering the state of the traffic light. (It's at least a better example than the gorilla suit fiasco.) It's difficult to come up with non-silly examples, but here's an attempt:

Alex is a maintenance worker and is investigating reports of a malfunctioning coffee machine. He has a temperature gauge hooked up to the machine and has been watching it. If the temperature ever rises above 220 F, he is required to dismantle the machine for repairs -- currently it sits at 219. Bob has been waiting for fresh coffee for some time, and eventually cuts in front of Alex, obscuring his view. Bob brews a pot of coffee, and during the brewing, the temperature rises to 221. By the time Bob has finished and left, the gauge has returned to 219.

Due to Bob's actions, the state of the machine exceeded the trigger point, and Alex should have dismantled the machine. However, because his process was blocked by Bob, he never observed that change, so instead he shrugs and leaves the machine alone. 174.47.210.5 (talk) 19:11, 17 August 2017 (UTC)

'Examples' not relating to the actual subject matter of this article (i.e. multithreaded computing) don't belong here at all.

I have removed a ridiculous anecdote about waiting at traffic lights. It has nothing whatsoever to do with computing, and even as an analogy only adds confusion. If Wikipedia can't explain something without having to resort to irrelevant waffle about other things entirely, it shouldn't try to explain them at all. 2A00:23C1:8250:6F01:5C80:7552:C89E:C5FE (talk) 01:07, 20 March 2018 (UTC)

• while the example removed was indeed unfortunate (it didn't show Bob making wrong decisions due to ABA), the tradition of illustrating computing problems - and ESPECIALLY multithreading problems - with non-computing analogies (referred to above as "irrelevant waffle"), is a long-standing and IMNSHO very useful one (see, for example, Dining Philosophers analogy), so if a better example of similar nature appears - I will be all for keeping it. Ipsign (talk) 04:49, 23 July 2018 (UTC)