lundi 2 novembre 2015

How can I prevent undefined behavior and the ABA issue in this lock-free stack function?

I'm currently working on a lock-free singly linked list in C++11, and I'm having an issue with my popFront() function - or I should at least say I know that it will have problems in certain instances.

In any case, this is what I currently have:

std::shared_ptr<T> popFront(void)
{
    auto p = atomic_load(&head);
    while(p && !atomic_compare_exchange_weak(&head, &p, p->next))
    {}
    return p ? p->data : std::shared_ptr<T>();
}

Note that head is of type shared_ptr.

However, I'm anticipate a few issues. The first being the situation in which two threads are executing popFront(), they both read the same head, and one thread finishes first. Before the second thread finishes, the caller deletes the object that was being pointed to, so the second thread is now working with deleted memory. The second issue is the classic ABA problem.

The idea behind this linked list is to have it be lock-free, so I want to avoid imposing a lock within this function. Unfortunately, though, I'm not sure how to address these issues. Any suggestions would be appreciated.

Aucun commentaire:

Enregistrer un commentaire