[Insight-developers] itkTimeStamp Test Failures Mistery

[Tom Vercauteren]

Hi all,


First of all, if anyone knows the answer to that question please answer!
When several threads assign the same integer variable at the same
time, is it possible that the value of the integer be corrupted or can
we safely assume that the value of the integer will be one of those
trying to be assigned by the threads?


Now back to the TimeStamp bug. Looking at the latest dashboard, it
confirms that the assignment really is the culprit.

The problem is that we have one single TimeStamp Object that is
modified by several threads at the same time.

Thanks to the atomic increment, the global time index is correct.
However, the actual modified time of the TimeStamp Object may not be.
Let's take two threads, A and B. The following scenario is possible:
*) We start with a global counter g_mtime=0 and a local counter l_mtime=0
1) Thread A increments the global counter ( g_mtime=1,  l_mtime=0 )
2) Thread B increments the global counter ( g_mtime=2,  l_mtime=0 )
3) Thread B assigns the local counter ( g_mtime=2,  l_mtime=2 )
4) Thread A assigns the local counter ( g_mtime=2,  l_mtime=1 )

Here is how we get a different local and global counter. Now if
another thread say C is launched, what will happen is:
5) Thread C increments the global counter ( g_mtime=3,  l_mtime=1 )
6) Thread C assigns the local counter ( g_mtime=3,  l_mtime=3 )

And now we get back on our feet.

According to QT, the optimized timestamp is thus reentrant but not thread-safe:
http://doc.trolltech.com/4.4/threads.html#reentrancy-and-thread-safety
"By extension, a class is said to be reentrant if each and every one
of its functions can be called simultaneously by multiple threads on
different instances of the class. Similarly, the class is said to be
thread-safe if the functions can be called by different threads on the
same instance."

Note that this definition is subject to controversy (according to
wikipedia http://en.wikipedia.org/wiki/Reentrant_(subroutine)#Relation_to_thread_safety
"Every reentrant function is thread-safe, however, not every
thread-safe function is reentrant.").

Anyhow, no matter how we call that we need to make a decision. Let's
stay with QT's definition for now.

I believe that having a reentrant TimeStamp is enough. Indeed when
multiple threads call modified on the same object at the same time,
the modifiedtime of the object will be the mtime of any of those
threads which should actually be equivalent. Also even though I know
that this is not an acceptable reason, it seems that calling modified
on the same object by several threads never happens in ITK...

Now the only potential problem I see is that if, when several threads
assign the same integer variable at the same time, the value may be
corrupted. If this is the case, we should move towards a thread-safe
(as compared to reentrant) TimeStamp object.


If we settle for reentrant only, we need to modify the TimeStampTest.

If we go for thread-safe, we need to modify the TimeStamp
optimization. One possible way would be to have a mutex lock around
the optimized increments, but instead of having a global mutex, we
could have a local member mutex only. My feeling is that even though,
this would be slower that the current optimized version, this would
still mitigates the freezing periods that I have encountered with the
global mutex.

Any better solution is certainly welcome!


Sorry for this long email, but since I am not very familiar with all
that, I takes time to try and be clear.

Regards,
Tom


On Thu, Feb 19, 2009 at 16:06, Sean McBride <sean at rogue-research.com> wrote:
> On 2/18/09 5:48 PM, Tom Vercauteren said:
>
>>> It would probably be better if m_ModifiedTime itself was passed to the
>>> various atomic increment functions.  The "problem" there is that the
>>> type of m_ModifiedTime would need to be of different type/size on
>>> different platforms.
>>>
>>> I could attempt such a patch if you'd like...
>>
>>Is this possible? itkTimeStampTime has to be a global (static)
>>variable whereas m_ModifiedTime has to be local (member). So unless
>>there is an atomic function that does "increment one variable and
>>assign its value to another", I think I am missing something.
>
> Ahhh, I see.  OTOH, itkTimeStampTime is an implementation detail, it
> seems the class' public API doesn't require its existence.  Maybe we
> could somehow do without it?  Though I'm not seeing how, at the moment...
>
> --
> ____________________________________________________________
> Sean McBride, B. Eng                 sean at rogue-research.com
> Rogue Research                        www.rogue-research.com
> Mac Software Developer              Montréal, Québec, Canada
>
>
>