detection of inter-thread dependencies through condition variables

[ERSEK Laszlo-2]

Hi,

[0] states:


----------
     7.5. Hints and Tips for Effective Use of Helgrind

       3. Avoid POSIX condition variables

       [...]

       a solution to this problem that does not require source-level
       annotation of condition-variable wait loops is beyond the current
       state of the art.
----------


I respectfully ask if the following passage could be recommended for the
Waiter as a code transformation that pessimizes, but does not invalidate
the code. If this qualifies as "source-level annotation of
condition-variable wait loops", then I apologize for the noise. (I
interpret "source-level annotation" as specially formatted comments, or
#pragma's, or Valgrind-specific API calls etc.)


----------
     If your original code looks (as it should look) like

         pthread_mutex_lock(mx);
         while (!b) {
           pthread_cond_wait(cv, mx);
         }
         pthread_mutex_unlock(mx);

     Then consider inserting the following COMPILING_FOR_VALGRIND block:

         pthread_mutex_lock(mx);

         #ifdef COMPILING_FOR_VALGRIND
         {
           struct timespec epoch;
           int ret;

           epoch.tv_sec = 0;
           epoch.tv_nsec = 0;

           ret = pthread_cond_timedwait(cv, mx, &epoch);
           assert(ETIMEDOUT == ret || 0 == ret);
         }
         #endif

         while (!b) {
           pthread_cond_wait(cv, mx);
         }
         pthread_mutex_unlock(mx);
----------

1. The dependency on the condition variable is now unavoidable, no matter
the initial value of "b" right after acquiring "mx"; so Valgrind can see
the dependency unconditionally.

2. No matter the value of "ret" (0 or ETIMEDOUT), pthread_cond_timedwait()
will have released and re-acquired mutex "mx"; see [1]. This is new
mutex/condvar activity, but it shouldn't hurt too much performance-wise.

3. The clock selection (see [2]) of the condition variable shouldn't
matter with an absolute time barrier set to 0. The epoch of whichever
clock is selected happens in the past, thus pthread_cond_timedwait()
should return immediately.

4. pthread_cond_timedwait() introduces a cancellation point. This is
nothing new if (!b) holds, because pthread_cond_wait() is a cancellation
point anyway. If "b" is true, however, this cancellation point is new.
Shouldn't hurt too much, since the original waiter code can't predict the
value of "b" either, so it must be prepared for cancellation anyway.

5. If "ret" is ETIMEDOUT, then we've received no signal/broadcast for
sure; back to business as usual. If "ret" is 0, we have received a
signal/broadcast (or a spurious wakeup), but we'll still check "b" first,
so the code stays valid.


As said above, I apologize if this is obvious and already covered by the
exclusion of "source-level annotation".

Thanks,
lacos

[0] http://valgrind.org/docs/manual/hg-manual.html#hg-manual.effective-use
[1] http://www.opengroup.org/onlinepubs/000095399/functions/pthread_cond_timedwait.html
[2] http://valgrind.org/docs/manual/drd-manual.html#drd-manual.pctw

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

On Wed, Nov 4, 2009 at 11:52 PM, ERSEK Laszlo <lacos@...> wrote:

Hi,

[0] states:


----------
    7.5. Hints and Tips for Effective Use of Helgrind

      3. Avoid POSIX condition variables

      [...]

      a solution to this problem that does not require source-level
      annotation of condition-variable wait loops is beyond the current
      state of the art.

I think this section of helgrind docs is generally out of date (Julian, please confirm). 

Helgrind 3.5 is a pure happens-before detector and thus handles this case correctly. 

Same for DRD. 

If you want a hybrid detector (which finds more races and is more stable, but does indeed choke on cond vars), see e.g. here: 

http://code.google.com/p/data-race-test/wiki/DynamicAnnotations#pthread_cond_wait_loop

--kcc 

 

----------


I respectfully ask if the following passage could be recommended for the
Waiter as a code transformation that pessimizes, but does not invalidate
the code. If this qualifies as "source-level annotation of
condition-variable wait loops", then I apologize for the noise. (I
interpret "source-level annotation" as specially formatted comments, or
#pragma's, or Valgrind-specific API calls etc.)


----------
    If your original code looks (as it should look) like

        pthread_mutex_lock(mx);
        while (!b) {
          pthread_cond_wait(cv, mx);
        }
        pthread_mutex_unlock(mx);

    Then consider inserting the following COMPILING_FOR_VALGRIND block:

        pthread_mutex_lock(mx);

        #ifdef COMPILING_FOR_VALGRIND
        {
          struct timespec epoch;
          int ret;

          epoch.tv_sec = 0;
          epoch.tv_nsec = 0;

          ret = pthread_cond_timedwait(cv, mx, &epoch);
          assert(ETIMEDOUT == ret || 0 == ret);
        }
        #endif

        while (!b) {
          pthread_cond_wait(cv, mx);
        }
        pthread_mutex_unlock(mx);
----------

1. The dependency on the condition variable is now unavoidable, no matter
the initial value of "b" right after acquiring "mx"; so Valgrind can see
the dependency unconditionally.

2. No matter the value of "ret" (0 or ETIMEDOUT), pthread_cond_timedwait()
will have released and re-acquired mutex "mx"; see [1]. This is new
mutex/condvar activity, but it shouldn't hurt too much performance-wise.

3. The clock selection (see [2]) of the condition variable shouldn't
matter with an absolute time barrier set to 0. The epoch of whichever
clock is selected happens in the past, thus pthread_cond_timedwait()
should return immediately.

4. pthread_cond_timedwait() introduces a cancellation point. This is
nothing new if (!b) holds, because pthread_cond_wait() is a cancellation
point anyway. If "b" is true, however, this cancellation point is new.
Shouldn't hurt too much, since the original waiter code can't predict the
value of "b" either, so it must be prepared for cancellation anyway.

5. If "ret" is ETIMEDOUT, then we've received no signal/broadcast for
sure; back to business as usual. If "ret" is 0, we have received a
signal/broadcast (or a spurious wakeup), but we'll still check "b" first,
so the code stays valid.


As said above, I apologize if this is obvious and already covered by the
exclusion of "source-level annotation".

Thanks,
lacos

[0] http://valgrind.org/docs/manual/hg-manual.html#hg-manual.effective-use
[1] http://www.opengroup.org/onlinepubs/000095399/functions/pthread_cond_timedwait.html
[2] http://valgrind.org/docs/manual/drd-manual.html#drd-manual.pctw

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

On Thursday 05 November 2009, Konstantin Serebryany wrote:

> I think this section of helgrind docs is generally out of date (Julian,
> please confirm).
> Helgrind 3.5 is a pure happens-before detector and thus handles this case
> correctly.
> Same for DRD.

Unfortunately I think the docs are correct, and neither Helgrind nor DRD
can handle this properly.  The basic problem is that there can be a h-b
dependency which arises from the loop and values in memory, not from the
mx or cv, so the dependency is "invisible".

I believe Laszlo's comments are valid and correct, and an interesting
solution.  I'd have to stare at it more it be convinced it's correct,
but it looks plausible.

Laszlo, can you explain the background to this a bit?  How did you
come to be looking at this problem?  Does your solution help?

J

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

On Thu, Nov 5, 2009 at 11:15 AM, Julian Seward <jseward@...> wrote:

On Thursday 05 November 2009, Konstantin Serebryany wrote:

> I think this section of helgrind docs is generally out of date (Julian,
> please confirm).
> Helgrind 3.5 is a pure happens-before detector and thus handles this case
> correctly.
> Same for DRD.

Unfortunately I think the docs are correct, and neither Helgrind nor DRD
can handle this properly.

Hm. Why???

cond var should only be used between mutex lock/unlock and those create h-b arcs... 

Here is the test: http://code.google.com/p/data-race-test/source/browse/trunk/unittest/racecheck_unittest.cc#520

Helgrind, DRD and ThreadSanitizer (in pure happens-before mode) are silent here. 

ThreadSanitizer in the hybrid mode barks. 

void Waker() {

GLOB = 1;

MU.Lock();

COND = 1;

CV.Signal();

MU.Unlock();

}

void Waiter() {

usleep(100000); // Make sure the signaller gets first.

MU.Lock();

while(COND != 1)

CV.Wait(&MU);

MU.Unlock();

GLOB = 2;

}

 

 The basic problem is that there can be a h-b
dependency which arises from the loop and values in memory, not from the
mx or cv, so the dependency is "invisible".

I believe Laszlo's comments are valid and correct, and an interesting
solution.  I'd have to stare at it more it be convinced it's correct,
but it looks plausible.

Laszlo, can you explain the background to this a bit?  How did you
come to be looking at this problem?  Does your solution help?

J

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

[ERSEK Laszlo-2]

(Is SF broken? The web interface doesn't thread threads; whitespace
formatting is lost even though my message was plain text; I didn't receive
Julian's reply, even though I'm subscribed and receive commit logs and
other messages; and only two thirds of the calendar table fit into a
browser window 954 pixels wide.)


On Thu, Nov 5, 2009 at 11:15 AM, Julian Seward <jseward@...>
wrote:

> I believe Laszlo's comments are valid and correct, and an interesting
> solution. I'd have to stare at it more it be convinced it's correct, but
> it looks plausible.

Thank you. I figured it might not be completely useless if somebody can
compile her code with all these holding:
- the code stays correct,
- Valgrind headers are not installed -- no Valgrind specific ANNOTATE_*
   macros,
- Valgrind still sees the condvar dependency in the binary in any case.

(I think of this as a possible manual amendment, not a change to
valgrind's instrumentation. I have no idea whether that would be possible
at all.)


> Laszlo, can you explain the background to this a bit? How did you come
> to be looking at this problem?

I develop lbzip2 (see <200808180908.42503.jseward@...>), and the
sponsor of my lbzip2 Debian package, Paul Wise, mentioned valgrind. I said
I already tested with valgrind [0]. (Not because I was investigating a bug
-- I was simply curious.) However, this made me remember reading some
caveat in the Helgrind manual. I re-read that section and
pthread_cond_timedwait() just occurred to me.


> Does your solution help?

I didn't try it out. If we cannot prove it's correct (or worse, we can
disprove it), there's no need to. If we prove it correct, there's kinda no
need to either :)

Thanks,
lacos

[0] http://lists.debian.org/debian-mentors/2009/11/msg00060.html

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

On Thu, Nov 5, 2009 at 8:48 PM, ERSEK Laszlo <lacos@...> wrote:
> > Does your solution help?
>
> I didn't try it out. If we cannot prove it's correct (or worse, we can
> disprove it), there's no need to. If we prove it correct, there's kinda no
> need to either :)

Hello Laszlo,

Can you please post a small self-standing program or comment on
Konstantin's test program
(http://code.google.com/p/data-race-test/source/browse/trunk/unittest/racecheck_unittest.cc#520)
? I prefer commenting on a program that can be compiled and run
instead of commenting on incomplete program fragments.

Bart.

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

[ERSEK Laszlo-2]

On Thu, 5 Nov 2009, Bart Van Assche wrote:

> Can you please post a small self-standing program or comment on
> Konstantin's test program
> (http://code.google.com/p/data-race-test/source/browse/trunk/unittest/racecheck_unittest.cc#520)
> ? I prefer commenting on a program that can be compiled and run instead
> of commenting on incomplete program fragments.

Konstantin didn't get the false positives described in the manual. What I
proposed is only for the case when there's a false positive to avert, so
if there's no false positive then my proposition is automatically void.

I installed valgrind-3.5.0 from source and wrote a small program:

http://pastebin.com/f6a4181c2

(You'll have to hit enter after a second or so when running it.)

I didn't get any false positives either.

Cheers,
lacos

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

I don't see any difference between this test and mine. 

Pure happens-before detectors are silent, hybrid detectors report a (false) race. 

/usr/bin/gcc -Wall -Wextra -ansi -pedantic -o waittest -g3 waittest.c -l pthread 

% (sleep 1; echo) | ~/valgrind/trunk/inst/bin/valgrind --tool=drd -q    ./waittest

1

% (sleep 1; echo) | ~/valgrind/trunk/inst/bin/valgrind --tool=helgrind -q    ./waittest

1

% (sleep 1; echo) | tsan -q     ./waittest

==22239== ThreadSanitizerValgrind: pure-happens-before=no fast-mode=yes ignore-in-dtor=yes

1

% (sleep 1; echo) | tsan -q --fast-mode=no    ./waittest

==22719== ThreadSanitizerValgrind: pure-happens-before=no fast-mode=no ignore-in-dtor=yes

==22719== WARNING: Possible data race during read of size 4 at 0x601300: {{{

==22719==    T0 (locks held: {}):

==22719==     #0  main /tmp/waittest.c:79

==22719==   Concurrent write(s) happened at (OR AFTER) these points:

==22719==    T1 (locks held: {}):

==22719==     #0  produce /tmp/waittest.c:17

==22719==     #1  ThreadSanitizerStartThread ts_valgrind_intercepts.c:504

==22719==   Address 0x601300 is 0 bytes inside data symbol "msg_to_publish.2907"

==22719== }}}

==22719==

1

--kcc 

On Fri, Nov 6, 2009 at 1:38 AM, ERSEK Laszlo <lacos@...> wrote:

On Thu, 5 Nov 2009, Bart Van Assche wrote:

> Can you please post a small self-standing program or comment on
> Konstantin's test program
> (http://code.google.com/p/data-race-test/source/browse/trunk/unittest/racecheck_unittest.cc#520)
> ? I prefer commenting on a program that can be compiled and run instead
> of commenting on incomplete program fragments.

Konstantin didn't get the false positives described in the manual. What I
proposed is only for the case when there's a false positive to avert, so
if there's no false positive then my proposition is automatically void.

I installed valgrind-3.5.0 from source and wrote a small program:

http://pastebin.com/f6a4181c2

(You'll have to hit enter after a second or so when running it.)

I didn't get any false positives either.

Cheers,
lacos

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

On Thu, Nov 5, 2009 at 11:38 PM, ERSEK Laszlo <lacos@...> wrote:

> On Thu, 5 Nov 2009, Bart Van Assche wrote:
>
>> Can you please post a small self-standing program or comment on
>> Konstantin's test program
>> (http://code.google.com/p/data-race-test/source/browse/trunk/unittest/racecheck_unittest.cc#520)
>> ? I prefer commenting on a program that can be compiled and run instead
>> of commenting on incomplete program fragments.
>
> Konstantin didn't get the false positives described in the manual. What I
> proposed is only for the case when there's a false positive to avert, so
> if there's no false positive then my proposition is automatically void.
>
> I installed valgrind-3.5.0 from source and wrote a small program:
>
> http://pastebin.com/f6a4181c2

Regarding the test program: the pointer-to-integer 'protected' is
properly protected by locking, and the code that writes a value to
*protected and the code that reads *protected is synchronized via the
producer-consumer pattern. Helgrind and DRD will implicitly insert a
happens-before arc between the producer and consumer, but
ThreadSanitizer not. I believe that Konstantin proposed the
ANNOTATE_PCQ_*() annotations some time ago in order to allow explicit
annotation of the producer-consumer pattern in source code (see also
http://article.gmane.org/gmane.comp.debugging.valgrind.devel/8398).

P.S.: please use reply-all and don't modify the CC-list when replying.

Bart.

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

On Fri, Nov 6, 2009 at 10:26 AM, Bart Van Assche <bart.vanassche@...> wrote:

On Thu, Nov 5, 2009 at 11:38 PM, ERSEK Laszlo <lacos@...> wrote:
> On Thu, 5 Nov 2009, Bart Van Assche wrote:
>
>> Can you please post a small self-standing program or comment on
>> Konstantin's test program
>> (http://code.google.com/p/data-race-test/source/browse/trunk/unittest/racecheck_unittest.cc#520)
>> ? I prefer commenting on a program that can be compiled and run instead
>> of commenting on incomplete program fragments.
>
> Konstantin didn't get the false positives described in the manual. What I
> proposed is only for the case when there's a false positive to avert, so
> if there's no false positive then my proposition is automatically void.
>
> I installed valgrind-3.5.0 from source and wrote a small program:
>
> http://pastebin.com/f6a4181c2

Regarding the test program: the pointer-to-integer 'protected' is
properly protected by locking, and the code that writes a value to
*protected and the code that reads *protected is synchronized via the
producer-consumer pattern. Helgrind and DRD will implicitly insert a
happens-before arc between the producer and consumer, but
ThreadSanitizer not.

ThreadSanitizer in the pure happens-before mode (--pure-happens-before=yes, NOT default) will behave exactly like Helgrind and DRD (see my previous reply). 

 

I believe that Konstantin proposed the
ANNOTATE_PCQ_*()

These will work, but there is a separate annotation specifically for cond var case. 

http://code.google.com/p/data-race-test/wiki/DynamicAnnotations#pthread_cond_wait_loop 

 

annotations some time ago in order to allow explicit
annotation of the producer-consumer pattern in source code (see also
http://article.gmane.org/gmane.comp.debugging.valgrind.devel/8398).

P.S.: please use reply-all and don't modify the CC-list when replying.

Bart.

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

On Wed, Nov 4, 2009 at 9:52 PM, ERSEK Laszlo <lacos@...> wrote:

> ----------
>     7.5. Hints and Tips for Effective Use of Helgrind
>
>       3. Avoid POSIX condition variables
>
>       [...]
>
>       a solution to this problem that does not require source-level
>       annotation of condition-variable wait loops is beyond the current
>       state of the art.
> ----------

IMHO item 3 in section 7.5 of the Helgrind manual was correct for
previous Helgrind versions but is no longer correct for Helgrind
3.5.0. I have created a bugzilla item about this issue (see also
https://bugs.kde.org/show_bug.cgi?id=213383).

Bart.

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

[ERSEK Laszlo-2]

On Fri, 6 Nov 2009, Konstantin Serebryany wrote:

> I don't see any difference between this test and mine.

I'm pleased to hear this, because then we're on the same page what should
be tested and also because this means I didn't screw up too much.

My purpose was not to create a different test case. I was just unfamiliar
with the pthreads wrappers in your example. Further, I had the cursory
impression that the same globals, mutexes and condvars were re-used for
multiple tests and it made me uncomfortable to comment.

I just wanted a bare-bones test case on the lowest pthreads level, because
that's what all of us understand without any introduction.

Thanks,
lacos

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

[ERSEK Laszlo-2]

On Fri, 6 Nov 2009, Bart Van Assche wrote:

> https://bugs.kde.org/show_bug.cgi?id=213383

This answers my original question/proposition; thank you very much.

Cheers,
lacos

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers