ABA problem

[albertjin]

I have a quick try by replacing Apple's OSAtomicEnqueue/OSAtomicDequeue with this queue and my code crashes. I use OSAtomic* from system library because my naive lock-free singly linked list implementation suffers from ABA bug. Does this one deal with ABA problem?

[cameron314]

Yes, my queue isn't affected by ABA. The core algorithm doesn't work with linked lists, so ABA isn't a concern there; and the free list that I use internally for block reuse is specifically designed to be correct in face of ABA.

I'm not afraid I'm not familiar with Apple's OSAtomic primitives. Surely they're not susceptible to ABA either? I'm not entirely sure I understood your whole question correctly...

[albertjin]

Thanks. I have a second thought now. The way handling the link node should have some cooperation with enqueue/dequeue. Or I should not new/delete node directly, but let the queue manage all object allocations.

I'm referring to this,

void OSAtomicEnqueue( OSQueueHead *__list, void *__new, size_t __offset);
void * OSAtomicDequeue( OSQueueHead *__list, size_t __offset);

https://developer.apple.com/library/mac/documentation/System/Reference/OSAtomic_header_reference/

It requires user code to provide a member to construct a single-link list. Based on my testing, it seems to have solved ABA problem. The operation is guaranteed to be successful for any non-null node pointer. It follows FILO, and also there is FIFO as OSAtomicFifoDequeue/OSAtomicFifoEnqueue.

[cameron314]

Sorry, I'm not sure I understand what you're asking.

Are you trying to implement your own lock-free FILO linked list without Apple's primitives?
What exactly does this have to do with my queue?

[albertjin]

I misunderstood that your queue can work with pointers, and now I know that's not the case. But maybe you can provide similar API for linked lists without ABA problem.

[cameron314]

On the contrary, my queue actually can work with pointers, with no risk of ABA :-)
(Of course, then you have to allocate/free the objects yourself.)

Were you wanting to use OSAtomicFifoEnqueue/OSAtomicFifoDequeue instead? Or was that just because my queue wasn't working?

If my queue wasn't working for you, could you post a short example snippet of how you're using it?

[albertjin]

The whole program is a little complex. I just paste the code related to the queue. ① and ② crash exactly the same: sometimes segmentation fault, sometimes error of freeing non-allocated memory, sometimes never exits as expected. ③ works fine and seems never crash.

I now change to use a cached FIFO memory recycle approach instead of instant new/delete, strangely to see that only yours may hang on exit. The naive one works as expected many times, no fault, no unexpected hang, and I haven't met a problem so far.

① Naive

    // SyncFunc::next is a struct member of type SyncFunc *
    // std::condition_variable cv;
    // std::atomic<SyncFunc *> queue;
    bool put(SyncFunc *func) {
        auto p = queue.load(std::memory_order_relaxed);
        func->next = p;
        if (funcs.compare_exchange_weak(p, func, std::memory_order_release, std::memory_order_relaxed)) {
            cv.notify_one();
            return true;
        }
        return false;
    }

    bool get(SyncFunc *&p) {
        for (;;) {
            p = queue.load(std::memory_order_relaxed);
            if (p == 0) {
                return false;
            } else if (queue.compare_exchange_weak(p, p->next, std::memory_order_release, std::memory_order_relaxed)) {
                return true;
            }
        }
    }

② Yours

    bool put(SyncFunc *func) {
        if (queue.try_enqueue(func)) {
            cv.notify_one();
            return true;
        }
        return false;
    }

    bool get(SyncFunc *&p) {
        while (!queue.try_dequeue(p));
        return true;
    }

③ Apple's

    bool put(SyncFunc *func) {
        OSAtomicEnqueue(&queue, func, offsetof(SyncFunc, next));
        cv.notify_one();
        return true;
    }

    bool get(SyncFunc *&p) {
        p = (SyncFunc *)OSAtomicDequeue(&queue, offsetof(SyncFunc, next));
        return p != 0;
    }

[albertjin]

I have a quick try by replacing this queue with Apple's OSAtomicEnqueue/OSAtomicDequeue and my code crashes ...

should be...

I have a quick try by replacing Apple's OSAtomicEnqueue/OSAtomicDequeue with this queue and my code crashes ...

Sorry for the confusion. It does not work regardless memory recycle cached or not. I'll get the full source to you some time later.

[cameron314]

Thanks, that does clear up my confusion :-)

① is susceptible to ABA, as you've already discovered. Though it may seem to work for you when recycling memory, it will almost certainly fail eventually (e.g. under stress, or after you reboot, etc.).
② is not semantically equivalent to the others: First, try_enqueue fails if there's not enough room pre-allocated to the queue (and getting the initial size right is non-trivial -- I have to update the README regarding that, sorry). Second, get will get stuck in an infinite loop if called when the queue is empty.

The equivalent code would be:

bool put(SyncFunc *func) {
    if (queue.enqueue(func)) {
        cv.notify_one();
        return true;
    }
    return false;
}

bool get(SyncFunc *&p) {
    return queue.try_dequeue(p);
}

③ appears fine since apparently Apple takes care of ABA internally somehow.

In any case, you shouldn't be seeing a crash with ② (neither the version you posted nor the modified one I put here). Perhaps it's related to the way you're using the queue? I'd have to see a more complete example to figure out what's going on.

[albertjin]

Ah, I have made it work with the following wrapper. I realized that the constructor is actually an API. Otherwise simply calling try_enqueue() always fails.

template <typename Value>
class QueueMc {
    moodycamel::ConcurrentQueue<Value> queue;

public:
    QueueMc() : queue(1024) {
    }

    bool put(Value v) {
        return put(v, [](){});
    }

    template <typename Func>
    bool put(Value v, Func succeeded) {
        if (queue.try_enqueue(v)) {
            succeeded();
            return true;
        }
        return false;
    }

    bool get(Value &v) {
        return queue.try_dequeue(v);
    }
};

[cameron314]

Ah, that would explain the infinite loops :-) (Not the crashes, though -- are you sure those were caused by my queue?)

The only thing you have to be careful with when using try_enqueue is that the initial size usually has to be significantly bigger than the maximum number of elements you want to concurrently store, since internally the queue uses blocks of elements (and blocks are not reused until the block is completely empty). So just be aware that the 1024 you pass to the constructor is really an upper bound on the number of elements you can store, and the actual number will vary depending on the number of threads accessing the queue, the number of blocks that are partially-full internally, etc.

I'll update the README soon to better explain try_enqueue and how to properly compute the initial size required for the queue. Sorry for any confusion!

[cameron314]

I'm closing this for now. If you find something in the queue which you think is a bug, or if I haven't fully answered your question, feel free to reopen the issue.