There may be race between enqueue and dequeue

[quininer]

Consider a jiffy queue, headOfQueue and tailOfQueue point to same bufferList, called B,
and head has advanced to last node in list.

There are three threads at this time

• Thread X executes enqueue, obtains pointer of B through tailOfQueue.load()
• Thread Y executes enqueue, generates a new bufferList, and updates tailOfQueue
• Thread Z executes dequeue, because it judges headOfQueue != tailOfQueue, so B is released

Then thread X will access the B pointer, but B has been released by Z thread.

You said in the email

If X did not finish the enqueue process then it will not set "is_set" flag , which is done at the end and Z will not delete the buffer and will not return X's item

You may have misunderstood what I mean, the enqueue is done by Y, and X get an outdated pointer. X needs to access next field to get updated pointer, but because the bufferList obtained by X has been released, this will cause UAF.

This problem can be detected with ThreadSanitizer.

WARNING: ThreadSanitizer: data race (pid=1324466)
  Write of size 8 at 0x7b8000018088 by main thread:
    #0 free /build/gcc/src/gcc/libsanitizer/tsan/tsan_interceptors_posix.cpp:707 (libtsan.so.0+0x359f8)
    #1 my_align_free /tests/Jiffy/MpScQueue.h:33 (output+0x30d0)
    #2 MpScQueue<int>::dequeue(int&) /tests/Jiffy/MpScQueue.h:268 (output+0x30d0)
    #3 testMyqueue(int, int, unsigned long) /tests/Jiffy/test.cpp:40 (output+0x30d0)
    #4 main /tests/Jiffy/test.cpp:66 (output+0x25c5)

  Previous read of size 4 at 0x7b800001808c by thread T2:
    #0 MpScQueue<int>::enqueue(int const&) /tests/Jiffy/MpScQueue.h:286 (output+0x2994)
    #1 trace_thread_action(MpScQueue<int>&, unsigned long, int) /tests/Jiffy/test.cpp:21 (output+0x2994)
    #2 void std::__invoke_impl<void, void (*)(MpScQueue<int>&, unsigned long, int), std::reference_wrapper<MpScQueue<int> >, unsigned long, int>(std::__invoke_other, void (*&&)(MpScQueue<int>&, unsigned long, int), std::reference_wrapper<MpScQueue<int> >&&, unsigned long&&, int&&) /usr/include/c++/10.2.0/bits/invoke.h:60 (output+0x3782)
    #3 std::__invoke_result<void (*)(MpScQueue<int>&, unsigned long, int), std::reference_wrapper<MpScQueue<int> >, unsigned long, int>::type std::__invoke<void (*)(MpScQueue<int>&, unsigned long, int), std::reference_wrapper<MpScQueue<int> >, unsigned long, int>(void (*&&)(MpScQueue<int>&, unsigned long, int), std::reference_wrapper<MpScQueue<int> >&&, unsigned long&&, int&&) /usr/include/c++/10.2.0/bits/invoke.h:95 (output+0x3782)
    #4 void std::thread::_Invoker<std::tuple<void (*)(MpScQueue<int>&, unsigned long, int), std::reference_wrapper<MpScQueue<int> >, unsigned long, int> >::_M_invoke<0ul, 1ul, 2ul, 3ul>(std::_Index_tuple<0ul, 1ul, 2ul, 3ul>) /usr/include/c++/10.2.0/thread:264 (output+0x3782)
    #5 std::thread::_Invoker<std::tuple<void (*)(MpScQueue<int>&, unsigned long, int), std::reference_wrapper<MpScQueue<int> >, unsigned long, int> >::operator()() /usr/include/c++/10.2.0/thread:271 (output+0x3782)
    #6 std::thread::_State_impl<std::thread::_Invoker<std::tuple<void (*)(MpScQueue<int>&, unsigned long, int), std::reference_wrapper<MpScQueue<int> >, unsigned long, int> > >::_M_run() /usr/include/c++/10.2.0/thread:215 (output+0x3782)
    #7 execute_native_thread_routine /build/gcc/src/gcc/libstdc++-v3/src/c++11/thread.cc:80 (libstdc++.so.6+0xcfc23)

  Thread T2 (tid=1324469, finished) created by main thread at:
    #0 pthread_create /build/gcc/src/gcc/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5efab)
    #1 __gthread_create /build/gcc/src/gcc-build/x86_64-pc-linux-gnu/libstdc++-v3/include/x86_64-pc-linux-gnu/bits/gthr-default.h:663 (libstdc++.so.6+0xcfef9)
    #2 std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) /build/gcc/src/gcc/libstdc++-v3/src/c++11/thread.cc:135 (libstdc++.so.6+0xcfef9)
    #3 main /tests/Jiffy/test.cpp:66 (output+0x25c5)

SUMMARY: ThreadSanitizer: data race /tests/Jiffy/MpScQueue.h:33 in my_align_free

test code https://gist.github.com/quininer/3fd07999f341470466377617367d838d

[quininer]

cc @DolevAdas @s1ck

[CxdInitial]

Only occurred when the size of buffer list is zero. Am I right?

[quininer]

No, it can happen at any buffer list size.

[Donald-Rupin]

I was able to reproduce this in different tests. There needs to be a memory reclamation technique to avoid using the stale pointer in the implementation. Has anyone come up with a fix for this?

[ibraheemdev]

This is addressed in the paper, but not implemented here:

When preforming the fold, only the array is deleted, which consumes the most memory. The reason for not deleting the the entire array’s structure is to let enqueuers, who kept a pointer for tailOfQueue at line 4 of Algorithm 4, point to a valid BufferList at all times with the correct prev and next pointers. To delete the rest of the array structure later on, the dequeuer keeps this buffer in a list called garbageList, a member of the Jiffy class (line 54). When a BufferList from the queue is deleted, the dequeuer checks if there is a BufferList in garbageList that is before the buffer being deleted. If so, the dequeuer deletes it as well (lines 70- 75

[quininer]

@ibraheemdev This statement is too vague, and if garbageList's just a simple queue, then I doubt it will really solve the race problem.

garbageList can only defer the destruction of list until the next head is also filled. This may be less likely, but it is still unsound.
To ensure that the list is not destroyed before being used, some relationship must be established between use and release, such as using a memory reclamation mechanism.

I'm not sure if g→positionInQueue ¡ next→positionInQueue is trying to take that responsibility, but it's not enough anyway, since next→positionInQueue can be advance by the enqueuer without restriction.
In addition, moveToNextBuffer itself will destroy headOfQueue, so the list maybe destroyed without going through garbageList.

Anyway, I'd be happy if Jiffy was sound. I've always wanted a waitfree queue that doesn't rely on memory reclamation or thread_local.

[ibraheemdev]

@quininer Yeah, the garbage list does not do enough to solve the issue. FWIW, my testing shows that jiffy with full memory reclamation still performs very well.

[quininer]

@ibraheemdev This sounds good, but if memory reclamation is allowed, jiffy is less attractive than other queue designs based on memory reclamation.

[ibraheemdev]

Which other queue designs are you referring to?

[quininer]

@ibraheemdev I'm not referring to a specific queue, but I know that turn queue is designed for that.