Folding-Hyperspace

2012-07 Update

It seems I have misunderstood the Qt documentation on implicit sharing, and for good reason: it is not very clear. After asking a question about this at the Qt Wiki (I can't find it now or I would link it) I was told that the key to understanding this was that a copy of an implicitly shared object must be made with mutex protection, but the copy could be modified by another thread without using a mutex. For example, given thread #1 creates a list like this:

QList<object> myCopy;
myCopy.append(newThing);
...
// make a copy before starting thread #2 or protect with mutex during copy
QList<object> yourCopy=myCopy;
// create and start thread #2 which uses yourCopy
// more processing in thread #1 of myCopy

I can now in thread #2 do anything I like with yourCopy and not need to use a mutex to access it. Any other use example risks causing a thread conflict of the QList objects. As you can see, this isn't very useful for sharing objects between threads. Unless you specifically do it this way, you must use a mutex to access the list in both threads, and this example shows that the list quickly becomes out-of-date for thread #2 unless another copy is made, which requires a mutex. So what does this actually solve? You still need a mutex for most realistic use cases.

For some good suggestions on using QThread, I recommend you look at these articles:

Threads, Events and QObjects

You’re doing it wrong…

Threading without the headache

Atomic reference counting - is it worth it?

However, I still believe that the atomic dereference operations are not thread safe and could still lead to problems, even when making modifications to a copy of an implicitly shared object in a thread as specified in the documentation. When the object is dereferenced, there is a deep copy operation that takes place, and if the original thread is modifying the data during this time, corruption is sure to follow.

As a result, the example program given here is not an example of a failure of the Qt Implicit Sharing atomic optimizations because it breaks the rules. I will need to study this some more to see if I can create a true example of how this fails in real use. I can only say, be very careful how you use implicitly shared objects in threads.

Now back to the original post:

Implicit Sharing and Multi-Threading Problems

This article will discuss a multi-threading resource safety issue concerning the use of implicitly shared objects where a pointer is used to store the data and the object is reference counted when accessed to determine if a deep copy is needed (copy on change) or if it can be safely deleted when no longer used. I will show how this can lead to low failure rate access violations and heap corruption that happens much later after the original normally silent failure.

First, let us look at the Qt documentation on this subject (see www.trolltech.com for more on Qt):

Discussion and Product Framework Analysis

Paragraphs 1, 2 and 4 appear to say it is safe to copy shared objects between threads, but paragraph 3 doesn't. Paragraph 3 even suggests that read access between threads requires a mutex.

For reference, Borland doesn't appear to have any documentation on the subject of safe thread use of AnsiString which is also implicitly shared. A few years ago I noticed that it caused problems when copied between threads and fixed it by using the older non-shared ShortString, still available from the MS-DOS period.

From this information link, it appears the MFC CString is also reference counted:

http://www.codeguru.com/cpp/cpp/string/article.php/c2789__1

I could not find any information concerning any problems using CString across threads.

Objects and resources are heavily shared in the .NET environment, but I have not studied any problems with their thread use there. It is possible that the .NET virtual machine has special instructions to process the resource counting correctly during thread switching but I don't really know.

Problem Definition

To see how a problem could result from a copy between threads, examine the copy constructor and destructor of the Qt QDateTime shared object (which Trolltech forgot to include in their list of shared objects):

QDateTime::QDateTime(const QDateTime &other)
{
  d = other.d; // line #1
  d->ref.ref(); // line #2
}

QDateTime::~QDateTime()
{
  if (!d->ref.deref()) // line #3
  delete d; // line #4
}

Here is a sequence that will crash the copy constructor:

1. Assume a shared QDateTime has been created in thread 2 and the reference count is 1.
2. Thread 1 calls the copy constructor for this object and executes line 1.
3. A task switch occurs to thread 2.
4. Thread 2 calls the destructor of the object and executes lines 3 and 4.
5. Because the reference count is 1, thread 2 will dereference the object and delete it.
6. A task switch occurs back to thread 1.
7. Thread 1 now counts the reference up for a memory block on the heap free list on line 2.
8. The heap manager will quickly find a problem in the heap when in debug mode, but not until much later.

Another possible crash sequence is this:

1. Thread 2 calls the destructor on the copy it has and executes line 3.
2. A task switch occurs to thread 1.
3. Thread 1 copies the object and executes lines 1 and 2. The reference count is back to 1.
4. A task switch occurs to thread 2.
5. Thread 2 executes line 4 and deletes the object reference that is still in use by thread 1.

Here is a picture of a typical failure showing how the reference count changed the heap check value:

Programs running outside of debug control can simply disappear from the screen when they fault.

Test Programs

These programs were written to show off this problem. The Borland Development Studio 2006 C++ version will cause an access violation. The Visual Studio 2005 C++/Qt version will cause a heap corruption assert. The number of times the copy is executed in the inner loop will change the frequency of failure. A loop count of 1 may run for a long time, but set it from 10 to 20 and the failure will be very quick. You will need a compiler environment to use these programs, the necessary runtime DLLs are not included. They should not be run on any CPU slower than about 2 GHz or the high priority threads can freeze the GUI and block your machine.

Qvtk_Test_CRTL.zip The VS2005 C++ source code (24 KB).

BCB_DataShareTest.zip The BDS2006 C++ source code (18 KB).

Implications

There are some possible implications for the Qt framework because shared objects are often passed between threads by the signal-slot communications system and also the QMetaObject::invokeMethod() call. If for example, a thread emits a signal and passes a QString to a target slot on another thread and then quickly changes the QString, there is a possibility that a task switch could occur somewhere in this time frame and cause heap corruption. This is because the delivery of the QString to the target thread is delayed because it must pass through the event loop in the target thread to be received.

Conclusion

Implicitly shared objects can't be directly copied between threads as suggested in the Qt documentation. Worse, other product's threading documentation doesn't provide much (if any) warning on this subject and the specification of which framework objects and resources are shared is often incomplete.

A mutex must be used when making changes or copies of these types of objects across threads. If the object is only used in one thread then normal use applies. Most of the Qt shared objects are used only on the GUI thread so you may have never seen this problem. The increased use of multi-threaded processing on future multi-core CPUs may lead to problems unless you are careful when using shared objects.

Rapid failures only occur when making heavy use of object copies, and failure frequency varies greatly with CPU type, speed and your code mix. If object copies between threads don't happen often, the fault frequency can be on the order of hours or days.