1120579 - TSan: data race js/public/HeapAPI.h:279 GetGCThingMarkWordAndMask

Status: RESOLVED FIXED

(Core :: JavaScript: GC, defect)

Description

[Nathan Froyd [:froydnj]]

Attachment: tsan-js-gc-race.txt

[cribbing from decoder's script, hopefully he won't mind]

The attached logfile shows a thread/data race detected by TSan (ThreadSanitizer).

Typically, races reported by TSan are not false positives, but it is possible that the race is benign. Even in this case though, we should try to come up with a fix unless this would cause unacceptable performance issues. Also note that seemingly benign races can possibly be harmful (also depending on the compiler and the architecture) [1].

If the bug cannot be fixed, then this bug should be used to either make a compile-time annotation for blacklisting or add an entry to the runtime blacklist.

CC'ing jonco this time, as he was pointed out as a worthy investigator for bug 1125045, and the stacks here look similar to ones there.  I considered duping this one with bug 844755, but the underlying causes look different, and the fix there clearly didn't work for this bug...

[1] http://software.intel.com/en-us/blogs/2013/01/06/benign-data-races-what-could-possibly-go-wrong

Comment 1

[Andrew McCreight [:mccr8]]

This looks like UnmarkGrayChildren and background finalization racing.

Comment 2

[Jon Coppeard (:jonco)]

(In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #0)
> bug 1125045

That doesn't seem to be a valid bug - which one did you mean?

I think this race is benign.  Gray unmarking transitions the mark state for a cell from gray to black, and the background marking thread checks whether a cell is marked either gray or black.  So if bother operations happen on a single cell, the result is the same whichever order they end up in - the cell is not freed by the background sweeping thread, and the cell ends up marked black.

Comment 3

[Nathan Froyd [:froydnj]]

(In reply to Jon Coppeard (:jonco) from comment #2)
> (In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #0)
> > bug 1125045
> 
> That doesn't seem to be a valid bug - which one did you mean?

I meant bug 1120545!  Sorry about that.

> I think this race is benign.  Gray unmarking transitions the mark state for
> a cell from gray to black, and the background marking thread checks whether
> a cell is marked either gray or black.  So if bother operations happen on a
> single cell, the result is the same whichever order they end up in - the
> cell is not freed by the background sweeping thread, and the cell ends up
> marked black.

I think I can believe that.  Julian sounded skeptical, so there might be something here we're both missing!

I see that ChunkBitmap::isMarked is already marked MOZ_TSAN_BLACKLIST, and clearly that's not helping.  Would it be awful if we used Atomic<uintptr_t, Relaxed> elements for the mark bitmap, so TSan would be able to tell that we're willing to access this from multiple threads, and we're willing to pay the consequences if something goes wrong?  It shouldn't affect the codegen at all.  (Well, except maybe GCC 4.6...should check that...)

Comment 4

[Jon Coppeard (:jonco)]

(In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #3)

> Julian sounded skeptical, so there might be something here we're both missing!

Quite possible, if there's an example where this doesn't work please let us know!

> Would it be awful if we used Atomic<uintptr_t,
> Relaxed> elements for the mark bitmap, so TSan would be able to tell that
> we're willing to access this from multiple threads, and we're willing to pay
> the consequences if something goes wrong?  It shouldn't affect the codegen
> at all.  (Well, except maybe GCC 4.6...should check that...)

I would be fine with that if it doesn't affect mark performance.  Does relaxed really not affect codegen?  I guess for bitwise and and or operations it shouldn't but I think we have to check that.

Comment 5

[Lars T Hansen [:lth]]

(In reply to Jon Coppeard (:jonco) from comment #4)
> 
> Does relaxed really not affect codegen?

I think it may in principle affect codegen, but that it won't, on current platforms for aligned data up to the size of a pointer.

For one thing, a relaxed access has to be atomic also in the sense that there's no tearing, so if the hardware does not guarantee that then there may be some overhead to guarantee that a consistent value is read or written.

For another thing, I believe one motivation for making all data races undefined in C++ is to allow multithreaded C++ to be used on platforms with hardware race detection (I think I have that from Boehm and Adve's paper on the C++ memory model).  On such a platform, an explicitly relaxed access would have to disable race detection for the access, probably by means of a different type of load/store instruction.

I don't know of any modern mainstream platforms that have tearing issues for up-to-pointer-size aligned data or hardware race detection.  (I've looked, and found none; if anyone knows different I'd love to know.)  So a relaxed load or store should compile to a normal load or store.

Comment 6

[Jon Coppeard (:jonco)]

(In reply to Lars T Hansen [:lth] from comment #5)
I tried this out and clang didn't insert any barriers but it did generate LOCK, ORQ rather than just ORQ for the update.

Comment 7

[Lars T Hansen [:lth]]

(In reply to Jon Coppeard (:jonco) from comment #6)
> (In reply to Lars T Hansen [:lth] from comment #5)
> I tried this out and clang didn't insert any barriers but it did generate
> LOCK, ORQ rather than just ORQ for the update.

For a relaxed atomic?  That's surprising (to me anyhow), and interesting.  After all the lock has the effect of a barrier.

(Wasn't this why we couldn't use the C++11 relaxed atomics with MSVC 2012 - it used a lock where none was really needed?)

Comment 8

[Lars T Hansen [:lth]]

(In reply to Lars T Hansen [:lth] from comment #7)
> (In reply to Jon Coppeard (:jonco) from comment #6)
> > (In reply to Lars T Hansen [:lth] from comment #5)
> > I tried this out and clang didn't insert any barriers but it did generate
> > LOCK, ORQ rather than just ORQ for the update.
> 
> For a relaxed atomic?  That's surprising (to me anyhow), and interesting. 
> After all the lock has the effect of a barrier.
> 
> (Wasn't this why we couldn't use the C++11 relaxed atomics with MSVC 2012 -
> it used a lock where none was really needed?)

Ah, but you did a read-modify-write operation, did you not?  Then the lock makes sense.  I was thinking separate loads and stores.  Can you post the code?

Comment 9

[Jon Coppeard (:jonco)]

(In reply to Lars T Hansen [:lth] from comment #8)
> Ah, but you did a read-modify-write operation, did you not?  Then the lock
> makes sense.  I was thinking separate loads and stores.  Can you post the
> code?

Yes, this is for ChunkBitmap::markIfUnmarked(): 

https://dxr.mozilla.org/mozilla-central/source/js/src/gc/Heap.h#858

Comment 10

[Lars T Hansen [:lth]]

Just to see this through to the end...

Clang++-3.5 on X64.  Example program:

  #include <atomic>

  std::atomic<int> v;

  void update1(int bits) {
    int x = v.load(std::memory_order_relaxed);
    v.store(x | bits, std::memory_order_relaxed);
  }

  void update2(int bits) {
    v.fetch_or(bits, std::memory_order_relaxed);
  }

Output, edited:

  update1:
        movl    v(%rip), %eax
        orl     %edi, %eax
        movl    %eax, v(%rip)
        retq

  update2:
        lock
        orl     %edi, v(%rip)
        retq

I'd say this is as expected; independent relaxed loads and stores turn into regular loads and stores, but the read-modify-write gets a lock to remain indivisible.

Comment 11

[Kris Wright :KrisWright]

This is another old stack trace that doesn't appear to exist anymore. I'm closing out this bug, if there's an equivalent modern-day data race then tsan should already have a bug for it.