|
From: Greg P. <gp...@ap...> - 2010-01-29 21:34:57
|
On Jan 29, 2010, at 2:56 AM, Bart Van Assche wrote: > On Fri, Jan 29, 2010 at 11:48 AM, Konstantin Serebryany > <kon...@gm...> wrote: >> >> hm. maybe. dunno. >> Usually, such checking is hacked into the implementation of the >> synchronization utlility itself... No? > > The POSIX spec is ambiguous about reinitialization. Two quotes from > http://www.opengroup.org/onlinepubs/000095399/functions/pthread_barrier_init.html: > * The results are undefined if pthread_barrier_init() is called > specifying an already initialized barrier. > * [EBUSY] The implementation has detected an attempt to reinitialize a > barrier while it is in use (for example, while being used in a > pthread_barrier_wait() call) by another thread. > > Or: while it is specified that reinitializing an already initialized > barrier yields undefined results, it is not specified that > pthread_barrier_init() must return an error code when reinitializing a > barrier that is not in use. It is also not specified that pthread_barrier_init() must return an error code when reinitializing a barrier that is in use. Note that EBUSY is "may fail", not "shall fail". That means the implementation is allowed to return that error, but the implementation is also allowed to omit that safety check completely. The behavior of reinitialization is undefined. The meaning of EBUSY is defined, but the implementation is free to do something else instead. -- Greg Parker gp...@ap... Runtime Wrangler |
|
From: Konstantin S. <kon...@gm...> - 2010-01-29 11:07:11
|
On Fri, Jan 29, 2010 at 2:09 PM, Julian Seward <js...@ac...> wrote: > > > * Some barrier implementations (e.g. the one in libgomp) allow barrier > > reinitialization while others (e.g. POSIX threads) do not allow this. > > If we want threading tools to be able to complain about barrier > > reinitialization for barrier types for which this is not allowed we > > need a third argument for ANNOTATE_BARRIER_INIT() that tells the tool > > whether or not reinitialization is allowed. > > Yes, +1 for that. > So, what would be the code like? /* Report that the "barrier" has been initialized with initial "count". If allow_reinitialization is true, barrier_init() is allowed to be called multiple times w/o calling barrier_destroy() */ #define ANNOTATE_BARRIER_INIT(barrier, count, allow_reinitialization) ? > > Can you also do the other changes we discussed, so that the different > annotation sets can stay in sync? > > * get rid of ANNOTATE_UNPUBLISH and ANNOTATE_PUBLISH > I can't just remove them, there are used in several places. I already marked them as DEPRECATED. > > * rename ANNOTATE_HAPPENS_BEFORE(obj) > to ANNOTATE_HAPPENS_BEFORE_ACCUMULATE(obj) > maybe add a #define for backwards compatibility > > * add ANNOTATE_HAPPENS_BEFORE_OVERWRITE(obj) > > * add ANNOTATE_HAPPENS_BEFORE_FORGET(obj) > I will, as a separate change. > > J > |
|
From: Bart V. A. <bva...@ac...> - 2010-01-29 11:12:40
|
On Fri, Jan 29, 2010 at 12:06 PM, Konstantin Serebryany <kon...@gm...> wrote: > > > On Fri, Jan 29, 2010 at 2:09 PM, Julian Seward <js...@ac...> wrote: >> >> > * Some barrier implementations (e.g. the one in libgomp) allow barrier >> > reinitialization while others (e.g. POSIX threads) do not allow this. >> > If we want threading tools to be able to complain about barrier >> > reinitialization for barrier types for which this is not allowed we >> > need a third argument for ANNOTATE_BARRIER_INIT() that tells the tool >> > whether or not reinitialization is allowed. >> >> Yes, +1 for that. > > So, what would be the code like? > /* Report that the "barrier" has been initialized with initial "count". > If allow_reinitialization is true, barrier_init() is allowed to be called > multiple times > w/o calling barrier_destroy() */ > #define ANNOTATE_BARRIER_INIT(barrier, count, allow_reinitialization) > ? Maybe "reinitialization_allowed" instead of "allow_reinitialization" ? Bart. |
|
From: Konstantin S. <kon...@gm...> - 2010-01-29 11:24:09
|
PTAL (==please take a[nother] look) http://codereview.appspot.com/196059/patch/11/1005 On Fri, Jan 29, 2010 at 2:12 PM, Bart Van Assche <bva...@ac...> wrote: > On Fri, Jan 29, 2010 at 12:06 PM, Konstantin Serebryany > <kon...@gm...> wrote: > > > > > > On Fri, Jan 29, 2010 at 2:09 PM, Julian Seward <js...@ac...> wrote: > >> > >> > * Some barrier implementations (e.g. the one in libgomp) allow barrier > >> > reinitialization while others (e.g. POSIX threads) do not allow this. > >> > If we want threading tools to be able to complain about barrier > >> > reinitialization for barrier types for which this is not allowed we > >> > need a third argument for ANNOTATE_BARRIER_INIT() that tells the tool > >> > whether or not reinitialization is allowed. > >> > >> Yes, +1 for that. > > > > So, what would be the code like? > > /* Report that the "barrier" has been initialized with initial "count". > > If allow_reinitialization is true, barrier_init() is allowed to be > called > > multiple times > > w/o calling barrier_destroy() */ > > #define ANNOTATE_BARRIER_INIT(barrier, count, allow_reinitialization) > > ? > > Maybe "reinitialization_allowed" instead of "allow_reinitialization" ? > > Bart. > |
|
From: Konstantin S. <kon...@gm...> - 2010-02-02 13:15:56
|
I submitted the new barrier annotations, please check. http://code.google.com/p/data-race-test/source/browse/trunk/dynamic_annotations/dynamic_annotations.h#276 --kcc On Fri, Jan 29, 2010 at 2:23 PM, Konstantin Serebryany < kon...@gm...> wrote: > PTAL (==please take a[nother] look) > http://codereview.appspot.com/196059/patch/11/1005 > > > On Fri, Jan 29, 2010 at 2:12 PM, Bart Van Assche <bva...@ac...>wrote: > >> On Fri, Jan 29, 2010 at 12:06 PM, Konstantin Serebryany >> <kon...@gm...> wrote: >> > >> > >> > On Fri, Jan 29, 2010 at 2:09 PM, Julian Seward <js...@ac...> wrote: >> >> >> >> > * Some barrier implementations (e.g. the one in libgomp) allow >> barrier >> >> > reinitialization while others (e.g. POSIX threads) do not allow this. >> >> > If we want threading tools to be able to complain about barrier >> >> > reinitialization for barrier types for which this is not allowed we >> >> > need a third argument for ANNOTATE_BARRIER_INIT() that tells the tool >> >> > whether or not reinitialization is allowed. >> >> >> >> Yes, +1 for that. >> > >> > So, what would be the code like? >> > /* Report that the "barrier" has been initialized with initial >> "count". >> > If allow_reinitialization is true, barrier_init() is allowed to be >> called >> > multiple times >> > w/o calling barrier_destroy() */ >> > #define ANNOTATE_BARRIER_INIT(barrier, count, allow_reinitialization) >> > ? >> >> Maybe "reinitialization_allowed" instead of "allow_reinitialization" ? >> >> Bart. >> > > |
|
From: Julian S. <js...@ac...> - 2010-02-05 15:36:02
|
Looks ok to me. J On Tuesday 02 February 2010, Konstantin Serebryany wrote: > I submitted the new barrier annotations, please check. > http://code.google.com/p/data-race-test/source/browse/trunk/dynamic_annotat >ions/dynamic_annotations.h#276 > > --kcc > > On Fri, Jan 29, 2010 at 2:23 PM, Konstantin Serebryany < > > kon...@gm...> wrote: > > PTAL (==please take a[nother] look) > > http://codereview.appspot.com/196059/patch/11/1005 > > > > On Fri, Jan 29, 2010 at 2:12 PM, Bart Van Assche <bva...@ac...>wrote: > >> On Fri, Jan 29, 2010 at 12:06 PM, Konstantin Serebryany > >> > >> <kon...@gm...> wrote: > >> > On Fri, Jan 29, 2010 at 2:09 PM, Julian Seward <js...@ac...> wrote: > >> >> > * Some barrier implementations (e.g. the one in libgomp) allow > >> > >> barrier > >> > >> >> > reinitialization while others (e.g. POSIX threads) do not allow > >> >> > this. If we want threading tools to be able to complain about > >> >> > barrier reinitialization for barrier types for which this is not > >> >> > allowed we need a third argument for ANNOTATE_BARRIER_INIT() that > >> >> > tells the tool whether or not reinitialization is allowed. > >> >> > >> >> Yes, +1 for that. > >> > > >> > So, what would be the code like? > >> > /* Report that the "barrier" has been initialized with initial > >> > >> "count". > >> > >> > If allow_reinitialization is true, barrier_init() is allowed to be > >> > >> called > >> > >> > multiple times > >> > w/o calling barrier_destroy() */ > >> > #define ANNOTATE_BARRIER_INIT(barrier, count, > >> > allow_reinitialization) ? > >> > >> Maybe "reinitialization_allowed" instead of "allow_reinitialization" ? > >> > >> Bart. |
|
From: Bart V. A. <bva...@ac...> - 2010-03-08 08:27:44
|
On Fri, Jan 29, 2010 at 12:09 PM, Julian Seward <js...@ac...> wrote: > > [ ... ] > > Can you also do the other changes we discussed, so that the different > annotation sets can stay in sync? > > * get rid of ANNOTATE_UNPUBLISH and ANNOTATE_PUBLISH > > * rename ANNOTATE_HAPPENS_BEFORE(obj) > to ANNOTATE_HAPPENS_BEFORE_ACCUMULATE(obj) > maybe add a #define for backwards compatibility > > * add ANNOTATE_HAPPENS_BEFORE_OVERWRITE(obj) > > * add ANNOTATE_HAPPENS_BEFORE_FORGET(obj) (replying to an e-mail of about one month ago) Hello Julian, Can you please clarify how the proposed new annotation ANNOTATE_HAPPENS_BEFORE_OVERWRITE() differs from ANNOTATE_HAPPENS_BEFORE() and why it would be useful ? Bart. |
|
From: Julian S. <js...@ac...> - 2010-03-08 10:56:39
|
> Can you please clarify how the proposed new annotation > ANNOTATE_HAPPENS_BEFORE_OVERWRITE() differs from > ANNOTATE_HAPPENS_BEFORE() and why it would be useful ? I don't know; these are Konstantin's annotations; I did not propose them. (I also wondered what the difference was.) J |
|
From: Konstantin S. <kon...@gm...> - 2010-03-08 14:43:36
|
On Mon, Mar 8, 2010 at 2:14 PM, Julian Seward <js...@ac...> wrote:
>
>> Can you please clarify how the proposed new annotation
>> ANNOTATE_HAPPENS_BEFORE_OVERWRITE() differs from
>> ANNOTATE_HAPPENS_BEFORE() and why it would be useful ?
>
> I don't know; these are Konstantin's annotations;
Hm. Are they?
I am quite satisfied with what we have now.
Earlier, Julian suggested this:
> Can you also do the other changes we discussed, so that the different
> annotation sets can stay in sync?
> ...
> * rename ANNOTATE_HAPPENS_BEFORE(obj)
> to ANNOTATE_HAPPENS_BEFORE_ACCUMULATE(obj)
> maybe add a #define for backwards compatibility
> * add ANNOTATE_HAPPENS_BEFORE_OVERWRITE(obj)
> * add ANNOTATE_HAPPENS_BEFORE_FORGET(obj)
It would be interesting to see a *realistic* case where
ANNOTATE_HAPPENS_BEFORE_{OVERWRITE,FORGET} is indeed needed.
--kcc
> I did not
> propose them. (I also wondered what the difference was.)
>
> J
>
>
|
|
From: Julian S. <js...@ac...> - 2010-03-08 15:26:47
|
On Monday 08 March 2010, Konstantin Serebryany wrote: > On Mon, Mar 8, 2010 at 2:14 PM, Julian Seward <js...@ac...> wrote: > >> Can you please clarify how the proposed new annotation > >> ANNOTATE_HAPPENS_BEFORE_OVERWRITE() differs from > >> ANNOTATE_HAPPENS_BEFORE() and why it would be useful ? > > > > I don't know; these are Konstantin's annotations; > > Hm. Are they? Err, my mistake. Sorry. Yes I did propose these. But I think we should just forget them, and stay with ANNOTATE_HAPPENS_BEFORE and ANNOTATE_HAPPENS_AFTER. The motivation was for the correct annotation of barriers directly using h-b edges. But it's better to directly do so with ANNOTATE_BARRIER_*. The original idea was that, for a barrier, we have some abstract sync object (the barrier) which needs to acquire an h-b edge from each incoming thread. Then, when all the threads leave the barrier, they all take a h-b dependency from the sync object. So for the thread-arrival handling, ANNOTATE_HAPPENS_BEFORE is not the correct thing for the 2nd and subsequent arriving threads, because it throws away any previous h-b edge associated with the barrier. What we need is to accumulate h-b edges in the barrier; in VTS terms take the join (vector max) of all the VTSs of the threads arriving at the barrier. Hence the distinction between A_H_B_OVERWRITE(x), which copies the calling thread's VTS into 'x', and A_H_B_ACCUMULATE(x), which joins the calling thread's VTS into 'x'. J |
|
From: Bart V. A. <bva...@ac...> - 2010-03-08 19:08:39
|
On Mon, Mar 8, 2010 at 4:44 PM, Julian Seward <js...@ac...> wrote: > > [ ... ] > > But I think we should just forget them, and stay with > ANNOTATE_HAPPENS_BEFORE and ANNOTATE_HAPPENS_AFTER. > > The motivation was for the correct annotation of barriers directly using > h-b edges. But it's better to directly do so with ANNOTATE_BARRIER_*. > > The original idea was that, for a barrier, we have some abstract sync > object (the barrier) which needs to acquire an h-b edge from each incoming > thread. Then, when all the threads leave the barrier, they all take > a h-b dependency from the sync object. > > So for the thread-arrival handling, ANNOTATE_HAPPENS_BEFORE is not the > correct thing for the 2nd and subsequent arriving threads, because it > throws away any previous h-b edge associated with the barrier. What we > need is to accumulate h-b edges in the barrier; in VTS terms take the > join (vector max) of all the VTSs of the threads arriving at the barrier. > Hence the distinction between A_H_B_OVERWRITE(x), which copies the calling > thread's VTS into 'x', and A_H_B_ACCUMULATE(x), which joins the calling > thread's VTS into 'x'. I'm not sure I understood the above completely. What I understood about happens-before, happens-after annotations and barriers is as follows: * The effect of a happens-after annotation is that a new segment is created with as vector clock the maximum of the vector clock of the current thread and the vector clocks of the most recent matching happens-before annotations of all other threads. Any other implementation would make the reference counting annotation example in http://code.google.com/p/data-race-test/source/browse/trunk/dynamic_annotations/dynamic_annotations.h incorrect. * Annotating barriers with happens-before/after annotations is too complex to bother a user with. If I'm not mistaken it is possible to annotate POSIX barriers as follows with happens-before/after annotations (where b is a pointer to a pthread_barrier_t object and i is a thread-local integer variable with the same scope as the pthread_barrier_t object and initialized to zero): ANNOTATE_HAPPENS_BEFORE((char*)b + i) result = pthread_barrier_wait(b); ANNOTATE_HAPPENS_AFTER((char*)b + i) i = (i + 1) % 2; The complexity of the above is a compelling argument for me to introduce specific annotations for barriers. Notes: - The above annotation style is only correct if each time the same set of threads participates in the barrier. Annotating barriers with happens-before/after annotations is even more complex when the set of threads that participates in the barrier can vary. - Inserting ANNOTATE_HAPPENS_BEFORE(b) before each pthread_barrier_wait(b) call and ANNOTATE_HAPPENS_AFTER(b) after each pthread_barrier_wait(b) call is racy. There is a significant probability that not all ANNOTATE_HAPPENS_AFTER() annotations of the current barrier will have been invoked before the first ANNOTATE_HAPPENS_BEFORE() annotation of the next barrier is invoked. Bart. |
|
From: Bart V. A. <bva...@ac...> - 2010-03-09 11:09:03
|
On Wed, Jan 27, 2010 at 1:33 PM, Konstantin Serebryany <kon...@gm...> wrote: > > On Wed, Jan 27, 2010 at 3:41 PM, Julian Seward <js...@ac...> wrote: >> >> Konstantin, >> >> I'm trying to annotate a user-implemented barrier, using >> >> http://code.google.com/p/google-perftools/source/browse/trunk/src/base/dynamic_annotations.h >> specifically ANNOTATE_HAPPENS_BEFORE and ANNOTATE_HAPPENS_AFTER >> >> like this >> >> void barrier_wait ( barrier* b ) >> { >> ANNOTATE_HAPPENS_BEFORE(b); >> // the barrier implementation >> ANNOTATE_HAPPENS_AFTER(b); >> } > > this is exactly how I handle barrier. (replying to an e-mail of about one month ago) The above algorithm for annotating barriers is wrong. This can be illustrated easily via the test program drd/tests/pth_barrier in the Valgrind tree: DRD and Helgrind always report 32 races for this program when started with the arguments "2 32 1" (two threads, 32 iterations, silent output) while TSan reports zero races with silent output and 17 races with verbose output (arguments "2 32 0"). The results reported by DRD and Helgrind are correct, the results reported by TSan not. $ ../tsan/drt/tsan.sh drd/tests/pth_barrier 2 32 1 Extracting ThreadSanitizer to /tmp/valgrind.LbA93c ==1676== ThreadSanitizer, a data race detector ==1676== Copyright (C) 2008-2009, and GNU GPL'd, by Google Inc. ==1676== Using Valgrind-3.6.0.SVN and LibVEX; rerun with -h for copyright info ==1676== Command: drd/tests/pth_barrier 2 32 1 ==1676== ==1676== ThreadSanitizerValgrind r1819: pure-happens-before=yes fast-mode=no ignore-in-dtor=no ==1676== INFO: Allocating 939,524,096 (112 * 8,388,608) bytes for Segments. ==1676== ==1676== ThreadSanitizer summary: reported 0 warning(s) (0 race(s)) Sorry that I didn't have a closer look at the above algorithm earlier. Bart. |
|
From: Konstantin S. <kon...@gm...> - 2010-03-09 13:20:53
|
On Tue, Mar 9, 2010 at 2:08 PM, Bart Van Assche <bva...@ac...> wrote: > On Wed, Jan 27, 2010 at 1:33 PM, Konstantin Serebryany > <kon...@gm...> wrote: >> >> On Wed, Jan 27, 2010 at 3:41 PM, Julian Seward <js...@ac...> wrote: >>> >>> Konstantin, >>> >>> I'm trying to annotate a user-implemented barrier, using >>> >>> http://code.google.com/p/google-perftools/source/browse/trunk/src/base/dynamic_annotations.h >>> specifically ANNOTATE_HAPPENS_BEFORE and ANNOTATE_HAPPENS_AFTER >>> >>> like this >>> >>> void barrier_wait ( barrier* b ) >>> { >>> ANNOTATE_HAPPENS_BEFORE(b); >>> // the barrier implementation >>> ANNOTATE_HAPPENS_AFTER(b); >>> } >> >> this is exactly how I handle barrier. > > (replying to an e-mail of about one month ago) > > The above algorithm for annotating barriers is wrong. Yes, it may miss races. This is why we agreed to use ANNOTATE_BARRIER_* to implement barrier. > This can be > illustrated easily via the test program drd/tests/pth_barrier in the > Valgrind tree: DRD and Helgrind always report 32 races for this > program when started with the arguments "2 32 1" (two threads, 32 > iterations, silent output) while TSan reports zero races with silent > output and 17 races with verbose output (arguments "2 32 0"). The > results reported by DRD and Helgrind are correct, the results reported > by TSan not. tsan's implementation of ANNOTATE_BARRIER_* was incorrect though, I just fixed it (hopefully) Thanks for the report! Now tsan always reports one race (in non-verbose mode): ==17079== WARNING: Possible data race during write of size 4 at 0x4218060: {{{ ==17079== T2 (locks held: {}): ==17079== #0 threadfunc /home/kcc/valgrind/trunk/drd/tests/pth_barrier.c:57 ==17079== #1 ThreadSanitizerStartThread /home/kcc/drt/trunk/tsan/ts_valgrind_intercepts.c:553 ==17079== Concurrent write(s) happened at (OR AFTER) these points: ==17079== T1 (locks held: {}): ==17079== #0 threadfunc /home/kcc/valgrind/trunk/drd/tests/pth_barrier.c:57 ==17079== #1 ThreadSanitizerStartThread /home/kcc/drt/trunk/tsan/ts_valgrind_intercepts.c:553 ==17079== Location 0x4218060 is 0 bytes inside a block starting at 0x4218060 of size 8 allocated by T0 from heap: ==17079== #0 malloc /home/kcc/drt/t runk/tsan/ts_valgrind_intercepts.c:380 ==17079== #1 barriers_and_races /home/kcc/valgrind/trunk/drd/tests/pth_barrier.c:72 ==17079== #2 main /home/kcc/valgrind/trunk/drd/tests/pth_barrier.c:107 ==17079== }}} It does not report 32 races because it reports each stack only once. If you run the test in verbose mode you may get some more race reports like this: ==17079== WARNING: Possible data race during write of size 1 at 0x401A029: {{{ ==17079== T2 (locks held: {}): ==17079== #0 _IO_file_xsputn@@GLIBC_2.2.5 /usr/grte/v1/lib64/libc-2.3.6.so ==17079== #1 vfprintf /usr/grte/v1/lib64/libc-2.3.6.so ... This is because the test calls printf() from several threads w/o synchronization. ThreadSanitizer deliberately does not suppress these warnings by default because some users may consider it as a real problem (if you call printf from several threads w/o synchronization your output may be garbled). You can suppress or ignore these reports using the regular suppression mechanism or using tsan's ignore files. Thanks again! --kcc > > $ ../tsan/drt/tsan.sh drd/tests/pth_barrier 2 32 1 > Extracting ThreadSanitizer to /tmp/valgrind.LbA93c > ==1676== ThreadSanitizer, a data race detector > ==1676== Copyright (C) 2008-2009, and GNU GPL'd, by Google Inc. > ==1676== Using Valgrind-3.6.0.SVN and LibVEX; rerun with -h for copyright info > ==1676== Command: drd/tests/pth_barrier 2 32 1 > ==1676== > ==1676== ThreadSanitizerValgrind r1819: pure-happens-before=yes > fast-mode=no ignore-in-dtor=no > ==1676== INFO: Allocating 939,524,096 (112 * 8,388,608) bytes for Segments. > ==1676== > ==1676== ThreadSanitizer summary: reported 0 warning(s) (0 race(s)) > > Sorry that I didn't have a closer look at the above algorithm earlier. > > Bart. > |