How to test if a lock-free queue is correctly implemented?

Question

I implemented a lock-free queue with the GCC __sync_xxx_compare_and_swap atomic builtin. Now I want to make sure that my code is correct. So I started multiple threads for enqueueing and dequeueing, and tried to:

• measure the number of enqueue and dequeue operations, and check if they match
• measure the number of times an individual element is enqueued and dequeued, and check if that number for each element is two (1 enqueueing and 1 dequeueing)

I found that the above two results are correct, but how can I verify that the enqueueing order is exactly the same as the dequeueing order? Or, is there any way to check the correctness of my implementation?

Answer 1

Try Helgrind: a thread error detector. It's part of Valgrind. Be sure to read the manpage for extra goodies that can be enabled besides the default options.

As far as checking for re-ordering

1. generate only distinct items
2. log each action (en- & de-queue) for each thread in a per-thread log (a local variable in that thread, not a single global logfile!); this requires no synchronization
3. when each thread is about to end, save its log in a logfile.

When the program exits, you should then be able to match enqueues and dequeues in your logfile.

This is better than logging to a single logfile (protected by a mutex) during the test because it avoids a synchronization bottleneck (which would affect the thread dynamic and potentially make the test less relevant)