0

I trying to understand lock-free programming, and wrote a lock-free stack:

template <typename T>
class LockFreeStack
{
    struct Node
    {
        std::shared_ptr<T> data;
        Node* next;

        explicit Node(const T& _data)
            : data(std::make_shared<T>(_data)), next(nullptr)
        {}
    };
    std::atomic<Node*> head;

public:
    void push(const T& data)
    {
        auto n{new Node(data)};
        n->next = head.load();
        while (!head.compare_exchange_weak(n->next, n))
            ;
    }

    std::shared_ptr<T> pop(void)
    {
        auto old_head{head.load()};
        while (old_head && head.compare_exchange_weak(old_head, old_head->next))
            ;
        return old_head ? old_head->data : std::shared_ptr<T>{};
    }
};

And two thread for push/pop operation on:

static LockFreeStack<int> global_stack;

And main function:

int main(void)
{
    std::srand(std::time(nullptr));

    std::thread pushing_thread([](void) {
        for (size_t i{}; i < MAX_LENGTH; ++i)
        {
            const auto v{std::rand() % 10000};
            global_stack.push(v);

            std::cout << "\e[41mPoping: " << v << "\e[m" << std::endl;
        }
    });
    std::thread poping_thread([](void) {
        for (size_t i{}; i < MAX_LENGTH; ++i)
        {
            if (auto v{global_stack.pop()}; v)
            {
                std::cout << "\e[42mPushing: " << *v << "\e[m" << std::endl;
            }
        }
    });

    pushing_thread.join();
    poping_thread.join();
}

This program only run pushing_thread in Debug mode, but when i run the program with debugger it run both thread as expected or if i wait a moment between the threads:

std::thread pushing_thread(...);
std::this_thread::sleep_for(1s);
std::thread poping_thread(...);

It works properly. So what is happens when we run the program with debugger ?

  • Compiler: GCC 9.3.
  • Compiler flags: -std=c++2a -lpthread -Wall.
  • OS: ArchLinux with linux-5.5.13.
16
  • 1
    Please explain what exactly doesn't work. Commented Apr 1, 2020 at 17:53
  • @walnut, The poping_thread doesn't work in Debug mode. Commented Apr 1, 2020 at 17:56
  • 2
    Does it not pop? Does it corrupt your data? Does it hang? Does it crash? Commented Apr 1, 2020 at 17:57
  • 2
    @GhasemRamezani So, do you get a segmentation fault? Does it give wrong output? If so what is the output? Commented Apr 1, 2020 at 17:58
  • @GhasemRamezani stackoverflow.com/help/how-to-ask Commented Apr 1, 2020 at 17:58

2 Answers 2

1

This logic is flawed:

    while (old_head && head.compare_exchange_weak(old_head, old_head->next))
        ;

If old_head is not null and the exchanged worked then try again!

Sign up to request clarification or add additional context in comments.

Comments

1

Your implementation suffers from the so called ABA problem. Consider to the following scenario:

  • the stack looks like this: A->B->C (i.e., head points to A)
  • thread 1 loads the head (i.e., the address of A) and A's next pointer (B), but before it can perform the CAS, it is interrupted.
  • thread 2 pops A, then B, and then pushes A, i.e., the stack now looks like this: A->C
  • thread 1 resumes and happily updates the head from A to B -> your stack is corrupted - it looks like this: B->C - but B is currently in use by thread 2.

There are several possible solutions to avoid the ABA problem, like tagged pointers or concurrent memory reclamation schemes.

Update:
A tagged pointer is simply a pointer that is extended with a version counter, where the version tag is incremented every time the pointer is updated. You can either use DWCAS (Double-Width-CAS) to update a struct with a separate version field, or you can squeeze the version tag into the upper bits of the pointer. Not all architectures provide DWCAS instructions (x86 does), and it depends on the OS if the upper bits are unused (on Windows and Linux it is usually possible to use the 16 topmost bits).

On the topic of memory reclamation schemes I can refer you to my thesis: Effective memory reclamation for lock-free data structures in C++

1 Comment

@GhasemRamezani I have updated my answer to provide more details on the possible solutions for the ABA problem.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.