2

I am implementing a multi-threaded application in C++11 which uses a thread to poll data from a QUdpSocket (QT5 framework) and another one to process the collected data .

When incoming data is detected by the socket, a ReadyRead() signal is emitted and all datagrams are extracted from a QUdpSocket and copied into a std::list.

void SocketWrapper::QueuePendingDatagrams()
{    
  while (hasPendingDatagrams()) {
    int dataSize = pendingDatagramSize();
    QByteArray tmpQByte = receiveDatagram().data();
    datagramList.push_back(tmpQByte); // see const_data
  }
  emit newDatagrams(&datagramList);
}

In another thread, the consumer is then started and retrieves the first element of the list until the list is empty.

void Worker::ProcessDatagrams(std::list<QByteArray>* pDatagramList)
{
  while (pDatagramList->size() > 0) {
      QByteArray tmpDatagram = pDatagramList->front();
      pDatagramList->pop_front();

      // Process and log the data within the datagram...
}

My question is: As I am always popping the first element and pushing after the last one, is this lock-free approach thread-safe?

I might (and will) receive more data to the socket during the data processing so both threads will end up running at the same time. To me, it seems that the only data race that might occur could overestimate DatagramList->size() but I don't see why it would be a problem. If I continuously receive data, I believe that the whole list will be consumed anyway.

Bertinchamps
  • 113
  • 1
  • 5
  • 3
    Possible duplicate of [Threading-Safe std:list C++](https://stackoverflow.com/questions/38725768/threading-safe-stdlist-c) – Swift - Friday Pie Sep 12 '18 at 12:19
  • 2
    Any particular reason for using a list? Looks like a queue to me and moving data before popping is usually a good thing. –  Sep 12 '18 at 12:27
  • In my opinion, it is not a duplicate as, in @Swift-FridayPie's question, mutexes are used. If I understood well, it however provides the answer. Lists can not be shared by threads directly because it could lead to thread corruptions. – Bertinchamps Sep 12 '18 at 12:34
  • @Bertinchamps It's not exactly the same question but we generally use duplicates also to indicate "your answer may be found here". However in this instance it's kind of borderline so I'm leaving it – Lightness Races in Orbit Sep 12 '18 at 12:34
  • @OZ17 No particular reason for the List. I am pretty new to C++ and found out the list could be used for FIFO processing. I checked the difference here https://stackoverflow.com/questions/1262808/which-stl-container-should-i-use-for-a-fifo and I should indeed be using this kind of structure for the sake of clarity. – Bertinchamps Sep 12 '18 at 12:44
  • Very unsafe. There is no guarantee of thread safety here. – Galik Sep 12 '18 at 12:45
  • You're using Qt. You have QSemaphore and QQueue which give some shortcuts in implementation. Imho, linked list is not always the most optimal implementation of queue.. in most of realistic cases you'd like to have a cyclic buffer. E.g. allowing creation of infinite amount of requests may represent a Possible Weakness of system. – Swift - Friday Pie Sep 12 '18 at 18:52

2 Answers2

6

No.

You're on the right lines, but actually you can't call any container member function from different threads at the same time and expect it to work reliably, because the implementation of those member functions themselves are not [guaranteed to be] thread-safe.

I don't see why it would be a problem

Off the record, I'd agree that in the particular case of std::list I wouldn't expect much in the way of practical problems here. Some shops may consider this sufficient reason to go ahead and use this in production. I wouldn't accept it at code review though. The point is that we simply can't* know exactly what the innards do.

That being said, if you have some special stdlib implementation (or a stdlib implementation with a special flag/switch/option) that does provide this guarantee, then knock yourself out ;) * And at the end of the day you could inspect its code and make that determination for yourself, but honestly that way madness lies!

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • 3
    The O(1) complexity requirement on `size` implies problems are still likely – Caleth Sep 12 '18 at 12:24
  • @Caleth: Indeed - while this means a race inside `size()` is unlikely, I expect some small amount of state inside the container to be modified by this operations, though since this is likely not much more than integer increment/decrement operations, I'd be frankly astounded to witness real problems. But, still, code to spec.... – Lightness Races in Orbit Sep 12 '18 at 12:26
  • @Caleth: Actually, if you're performing some batch operation _maybe_ you could have a `size += n` situation and then there's trouble. But the list interface goes to substantial lengths to stop you from doing things like that anyway – Lightness Races in Orbit Sep 12 '18 at 12:27
  • @Caleth: Final note, above I've assumed that increment/decrement is inherently atomic on amd64 but I just realised I'm almost certainly thinking of something else, assignment to bool probably. Lol, whatever, doesn't matter, which is the point :) – Lightness Races in Orbit Sep 12 '18 at 12:28
  • 1
    producer `push_back`ing on an empty list whilst consumer reads `size` is a race. – Caleth Sep 12 '18 at 12:30
  • 1
    @Caleth Yes it is. Again, I was trying to talk about possible _practical outcomes_ of that race, but, again, it doesn't matter - the answer is simply _not to do this_ – Lightness Races in Orbit Sep 12 '18 at 12:32
  • @Caleth yeah.. it essentially suggest that std::list got some member field `_size` to store "supposed" size of linked list, which deepens the problem of race condition. – Swift - Friday Pie Sep 12 '18 at 18:50
3

NO

Imagine the list had just 1 element and your 2 threads tried to "simultaneously" push and pop.

If you have many elements, then popping an element off the front is unlikely to interact with the back pointer, and pushing an element on the back is unlikely to interfere with the front pointer, so the two operations /should/ be safe in terms of the list's integrity.

But clearly, when you pop the last element from the front, then the back pointer will also get updated, to say there are no more elements, and when you push an element to the back and the list is empty, then the front pointer is updated. Can you guarantee the order of those operations, and that they won't snaggle? You have protection for if the size is zero, but not for if the size is 1.

Another thing that concerns me is that since c++11 size() is an "instant" answer O(0), not a scan O(n), and to do this list keeps an integer count. If both push and pop modify the size counter "simultaneously", then they may snaggle and end up with an incorrect size value. If the internals of list use the value of size as an "is_empty()" check, perhaps to optimise inserting to an empty list, or popping the last element, then they may be fooled into performing inappropriate operations.

Gem Taylor
  • 5,381
  • 1
  • 9
  • 27