Fix race-condition in KRandom-seeding.
ClosedPublic

Authored by tfry on May 24 2017, 8:56 PM.

Details

Summary

Consider the following scenario: Thread A calls KRandom::random(), for the first time.
It will now go through a (relatively) expensive procedure to seed the RNG. Note that before
this patch, "init" is set to true long _before_ the actual call to qsrand().
Now, thread B calls KRandom::random() in this sensitive time window. Since it finds "init"
to be true, it will skip over the expensive initialization, and be very likely to arrive at
qrand(), before thread A had a chance to call qsrand().

This patch is the simplest possible solution: Making sure init is set, _after_ the seed was
really initialized. This does not prevent init races, but the worst case scenario is now, that
several threads are each going through the seeding. A more elaborate solution would be to
add mutex-protection during initialization.

Diff Detail

Repository
R244 KCoreAddons
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
tfry created this revision.May 24 2017, 8:56 PM
Restricted Application added a project: Frameworks. · View Herald TranscriptMay 24 2017, 8:56 PM
Restricted Application added a subscriber: Frameworks. · View Herald Transcript
tfry added a comment.May 24 2017, 9:20 PM

On further investigation, I see that qsrand() would probably have to be called for each thread, in any case. So that would mean keeping track of initialization state in a QThreadStorage<bool>?

rjvbb added a comment.May 24 2017, 9:27 PM

I was going to reflect that it would be better to set init in an atomic operation, but:

In D5966#111735, @tfry wrote:

On further investigation, I see that qsrand() would probably have to be called for each thread, in any case.

From the qsrand() documentation:
"The sequence of random numbers generated is deterministic per thread. For example, if two threads call qsrand(1) and subsequently call qrand(), the threads will get the same random number sequence."

That indeed probably means that if only thread 1 calls qsrand(), thread 2 will get the default, unseeded sequence.

So that would mean keeping track of initialization state in a QThreadStorage<bool>?

Or a simple QSet containing the thread ID, whichever is cheapest?

tfry updated this revision to Diff 14831.EditedMay 25 2017, 8:33 AM

Ensure proper per-thread random-seeding in KRandom::random().

As commented, the problem is somewhat different, than I thought, originally:

qsrand() and qrand() keep random seeds per QThread, and each thread needs a separate call
to qsrand(). Without this patch, qsrand() would only be called for the first thread to call
KRandom::random(). Any other thread will effectively use qsrand(1).

Note that prior to 9ae6d765b37135bbfe3a8b936e5a88b8a435e424 srand() and rand() were used.
Those are not properly thread-safe, but at least this would not result in threads using a
fixed seed.

mpyne added a subscriber: mpyne.May 26 2017, 1:15 AM

Would it be better to use QThreadStorage<bool> (to record if the thread has been seeded) instead of a QSet? It would allow us to more easily adopt C++11's thread_local once we remove support for older compilers. I also looked into whether we could adopt the higher-quality RNGs that should be available in C++11, but getting them seeded is apparently very difficult to do without introducing errors.

Also, I'd recommend using quintptr instead of intptr_t in the reinterpret_cast, as that seems more accurate for the semantics of XOR. The shift to XOR is a great idea though.

rjvbb added a comment.May 26 2017, 7:24 AM

Using QSet was my suggestion, if cheaper than QThreadStorage - something I didn't check, but I also didn't verify if QSet::insert is thread-safe.

About C++11: since when exactly does Qt require C++11 again?

tfry added a comment.May 26 2017, 7:45 AM
In D5966#111878, @rjvbb wrote:

but I also didn't verify if QSet::insert is thread-safe.

Ouch, you're right, it isn't. QThreadStorage it shall be, then (until we can use thread_local). That also handles thread-destruction, properly.

tfry updated this revision to Diff 14863.May 26 2017, 7:05 PM

Switch to QThreadStorage, use quintptr as suggested, add auto-test.

mpyne added a comment.May 29 2017, 5:46 PM

The changeset is fine to go in (once the duplicated semicolon is fixed).

As for C++11, I'm not aware that Qt requires C++11 as a blanket policy. Instead they require specific compilers, and then we can use the C++11 features supported by that compiler.

According to the Qt documentation, Qt 5.8 is the first Qt release to require at least GCC 4.8 across the board, on configurations using GCC. I believe that was the first GCC where thread_local is fully supported. Note that we do try to support MS Windows though, and MSVC as distributed with VS 2013 is the minimum requirement for both Qt 5.8 and current Qt development. But MSVC doesn't fully support thread_local until VS 2015. So it will probably be at least another couple of years before we can rely on that feature to be available.

src/lib/randomness/krandom.cpp
46

There are two semicolons on this line, only one is needed. :)

This revision was automatically updated to reflect the committed changes.
rjvbb added a comment.May 29 2017, 7:36 PM

I have no official reference for Qt requiring C++11, but I'm pretty sure I've seen the remark made on a mailing list or one of their code review tickets. I would have guessed that was with 5.7 but it can just as well be 5.8 and later. A GCC >= 4.8 *probably* corresponds to "we need complete enough C++11".

Supporting MSVC is a PITA: https://phabricator.kde.org/D5865

dfaure added inline comments.May 29 2017, 9:45 PM
autotests/krandomtest.cpp
168

variable size array, which is not in the standard.
https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard

Make size static to fix it.

178

The unittest doesn't check that at all. I guess it can't, reliably, but then what is the comment for?

179

QCOMPARE

aacid added a subscriber: aacid.May 29 2017, 10:39 PM
aacid added inline comments.
autotests/krandomtest.cpp
168

They are in C++11, no?

dfaure edited edge metadata.May 30 2017, 6:39 AM

No - not with this syntax. See the stackoverflow discussion I posted, or https://stackoverflow.com/questions/31645309/can-i-use-a-c-variable-length-array-in-c03-and-c11?rq=1

tfry added inline comments.May 30 2017, 6:41 AM
autotests/krandomtest.cpp
168

Sorry. Should have waited longer for your comment.

I thought "const int" was const... Will fix in a minute.

178

If the results are not unique, some of the results will already be in the set, and so results.insert() does not increase the size of the set. Only if each thread result is unique, the set size will correspond to the number of threads.

dfaure added inline comments.May 30 2017, 6:44 AM
autotests/krandomtest.cpp
178

Oh I see, you're right.