Eliminating Data Races in Firefox – A Technical Report [LWN.net]

The Mozilla Hacks site has a report on the use of ThreadSanitizer to detect and fix data races in the Firefox browser. "While benign data races do exist, we found that data races are very easily misclassified as benign. The reasons for this are clear: It is hard to reason about what compilers can and will optimize, and confirmation for certain 'benign' data races requires you to look at the assembler code that the compiler finally produces. Needless to say, this procedure is often much more time consuming than fixing the actual data race and also not future-proof. As a result, we decided that the ultimate goal should be a 'no data races' policy that declares even benign data races as undesirable due to their risk of misclassification, the required time for investigation and the potential risk from future compilers (with better optimizations) or future platforms (e.g. ARM)."

to post comments

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 6, 2021 16:56 UTC (Tue) by clugstj (subscriber, #4020) [Link] (17 responses)

Well, duh!

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 6, 2021 19:59 UTC (Tue) by willy (subscriber, #9762) [Link] (15 responses)

That's not "duh" at all. If you're looking at a statistic in order to make a decision, and it doesn't really matter if the statistic is wrong in 0.1% of the times, then you really don't want to put a lock around the statistic read.

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 6, 2021 21:54 UTC (Tue) by clugstj (subscriber, #4020) [Link] (5 responses)

So, your program crashing (or worse) 0.1% of the time is OK?

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 6, 2021 22:16 UTC (Tue) by willy (subscriber, #9762) [Link] (4 responses)

Of course not.

Your program deciding to optimise Basic Block A instead of Basic Block B 0.1% of the time isn't a problem.

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 6, 2021 22:45 UTC (Tue) by josh (subscriber, #17465) [Link] (2 responses)

> Your program deciding to optimise Basic Block A instead of Basic Block B 0.1% of the time isn't a problem.

It is if you're working on reproducible builds.

It's reasonable to use non-locking statistics for things like reporting resource usage to the user, where it isn't necessarily worth the performance hit just to give an accurate-to-the-byte statistic that's nonetheless still inaccurate the moment the lock is dropped.

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 6, 2021 22:53 UTC (Tue) by willy (subscriber, #9762) [Link] (1 responses)

I was trying to come up with a reasonable example for what a JavaScript interpreter might do. A C compiler has different tradeoffs (and most are single threaded as we get sufficient parallelism through splitting large files into small ones and using make -j, so there's little pressure to write a threaded C compiler)

I agree that reporting memory usage to the nearest byte, or indeed download speed might be better examples.

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 7, 2021 0:05 UTC (Wed) by josh (subscriber, #17465) [Link]

Ah, I see. Yes, a JIT compiler could absolutely use such statistics for runtime optimization decisions.

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 7, 2021 21:02 UTC (Wed) by iabervon (subscriber, #722) [Link]

I'd be worried about the possibility that the program optimizes Basic Block A using the properties of Basic Block B. Once you've got a data race where the behavior is undefined (which is what they're talking about), you can no longer assume that your variables each contain a single consistent value, and it seems perfectly plausible that a compiler would realize that only a data race could lead to "hottest" being different from what "block" was last time we read "block->types", and the rest of the CVE is obvious from there.

If you can arrange that your statistic read definitely produces some value (but you can't tell which one), then it's fine, but that's still a matter of eliminating the undefined behavior in every single case, which is what they proposed to do.

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 7, 2021 4:31 UTC (Wed) by luto (subscriber, #39314) [Link] (5 responses)

If you want to comply with the standards, avoid data races, avoid miscompilation, and still read statistics cleanly, you can use relaxed atomic reads. (Or READ_ONCE like Linux uses, although the degree to which that complies with the standards is arguably debatable.)

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 7, 2021 11:05 UTC (Wed) by pbonzini (subscriber, #60935) [Link] (1 responses)

In fact, until last week LWN had an awesome series on the topic. ;)

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 10, 2021 6:07 UTC (Sat) by milesrout (guest, #126894) [Link]

Did it go somewhere?

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 11, 2021 4:01 UTC (Sun) by suckfish (guest, #69919) [Link] (2 responses)

Working through the "standards compliance" bit recently with volatile / READ_ONCE type idioms, I came to the conclusion:

volatile is mostly left to "implementation defined" behaviour, and there is relatively little "undefined".
At least the ARM AAPCS gives you single-instruction-where-sane with volatile.
... and for data-types where single-instruction is not sane, you at least get only-access-the-bytes once.
I didn't check other ABI documents, I'm guessing they are similar.

As a result, READ_ONCE etc are covered by the combination of language-specs and ABI documents. I'm sure a language lawyer will jump in with more nauces & differences between specs etc.

You get what you expect: individual load & store operations with volatile can be used to build thread-safe code, but you need to understand the CPU you're running on, and explicitly fill in the gaps with memory-barriers and compare-exchange & locked instructions.

I must admit, I got a little less keen with C11/C++11 etc atomics a few years ago, when looking to do formal verification of some code, the state-of-the-art with the C11 atomics appeared to be academic papers concluding this was incredibly difficult and the specs were buggy. I fell back to modelling TSO with store buffers instead, at which point the only advantage of the standards based atomics is better readability. (A quick web search suggests the situation hasn't changed much since.)

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 11, 2021 14:33 UTC (Sun) by foom (subscriber, #14868) [Link] (1 responses)

This is a really useful tool for checking code against the c++ memory model: http://svr-pes20-cppmem.cl.cam.ac.uk/cppmem/help.html

It's a bit tricky to understand, but when you get it, it's quite powerful.

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 11, 2021 17:48 UTC (Sun) by suckfish (guest, #69919) [Link]

Thanks for the link. The work of the Cambridge group was the main academic work I had in mind above.

When I looked at CppMem 5 years ago, it seemed to be a great tool for the "litmus test" size examples that they were using to poke holes in the specs (e.g., a dozen lines of code), but didn't scale to the cases I was interested in (around 100 lines of code).

C.f., promela/spin which can handle larger examples, but doesn't help with anything weaker than sequential consistency (you can e.g., manual code processor store buffers, but going down that path rapidly increases code complexity and run-times).

I believe that much of the issue is inherent to the weaker memory models: the number of possible execution traces is much larger, limiting what the tools can cope with.

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 7, 2021 6:40 UTC (Wed) by epa (subscriber, #39769) [Link] (1 responses)

I guess in that case you need an explicit UNSAFE_READ macro to access it.

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 7, 2021 11:14 UTC (Wed) by foom (subscriber, #14868) [Link]

Well, in normal c++, you just use the standard atomic api for this, not a custom macro.

E.g. you make the value atomic:
std::atomic<int> foo;
and then ask to load it without memory barriers:
foo.load(std::memory_order_relaxed);

(And same in modern C, with a slightly different spelling)

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 8, 2021 0:21 UTC (Thu) by dancol (guest, #142293) [Link]

Maybe you don't need a lock, but a relaxed atomic read costs basically nothing and placates the data race police.

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 7, 2021 8:25 UTC (Wed) by sdalley (subscriber, #18550) [Link]

> Well, duh!

No. "Well done!"

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 8, 2021 0:47 UTC (Thu) by ncm (guest, #165) [Link] (2 responses)

It would be much better to use higher-level concurrency mechanisms that don't require sanitizer help. Standard C++ now has various mechanisms that often could be used. The goal is correctness by construction, so that if it compiles, it is correct.

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 8, 2021 1:28 UTC (Thu) by mathstuf (subscriber, #69389) [Link]

What mechanisms are those? I think you'd at least need a mutex that is templated over the data it protects as well as some way to prevent `mutable` existing on nominally `const` methods under read locks (though such code is now defined/expected to be threadsafe (or at least re-entrant) by the wording magic wand, but what code has actually been updated for that?).

Eliminating Data Races in Firefox – A Technical Report

Posted Apr 8, 2021 4:41 UTC (Thu) by roc (subscriber, #30627) [Link]

Suppose I want to apply a lambda to every element of an array, in parallel. What high-level concurrency mechanism does Standard C++ supply that ensures my lambda doesn't contain or reference any mutable state that is not thread-safe?