D5966: Fix race-condition in KRandom-seeding.

[David Faure]

dfaure added inline comments.

INLINE COMMENTS

> tfry wrote in krandomtest.cpp: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.

Oh I see, you're right.

REPOSITORY
  R244 KCoreAddons

REVISION DETAIL
  https://phabricator.kde.org/D5966

To: tfry, dfaure
Cc: aacid, mpyne, tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[Thomas Friedrichsmeier]

tfry added inline comments.

INLINE COMMENTS

> dfaure wrote in 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.

Sorry. Should have waited longer for your comment.

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

> dfaure wrote in krandomtest.cpp:178
> The unittest doesn't check that at all. I guess it can't, reliably, but then 
> what is the comment for?

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.

REPOSITORY
  R244 KCoreAddons

REVISION DETAIL
  https://phabricator.kde.org/D5966

To: tfry, dfaure
Cc: aacid, mpyne, tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[David Faure]

dfaure added a comment.


  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

REPOSITORY
  R244 KCoreAddons

REVISION DETAIL
  https://phabricator.kde.org/D5966

To: tfry, dfaure
Cc: aacid, mpyne, tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[Albert Astals Cid]

aacid added inline comments.

INLINE COMMENTS

> dfaure wrote in 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.

They are in C++11, no?

REPOSITORY
  R244 KCoreAddons

REVISION DETAIL
  https://phabricator.kde.org/D5966

To: tfry, dfaure
Cc: aacid, mpyne, tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[David Faure]

dfaure added inline comments.

INLINE COMMENTS

> krandomtest.cpp:168
> +const int size = 5;
> +KRandomTestThread* threads[size];
> +for (int i=0; i < size; ++i) {

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.

> krandomtest.cpp:178
> +}
> +// each thread should have returned a unique result
> +QVERIFY(results.size() == size);

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

> krandomtest.cpp:179
> +// each thread should have returned a unique result
> +QVERIFY(results.size() == size);
> +for (int i=0; i < size; ++i) {

QCOMPARE

REPOSITORY
  R244 KCoreAddons

REVISION DETAIL
  https://phabricator.kde.org/D5966

To: tfry, dfaure
Cc: mpyne, tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[René J . V . Bertin]

rjvbb added a comment.


  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

REPOSITORY
  R244 KCoreAddons

REVISION DETAIL
  https://phabricator.kde.org/D5966

To: tfry, dfaure
Cc: mpyne, tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[Thomas Friedrichsmeier]

This revision was automatically updated to reflect the committed changes.
Closed by commit R244:26a262180155: Ensure proper per thread seeding in 
KRandom. (authored by tfry).

CHANGED PRIOR TO COMMIT
  https://phabricator.kde.org/D5966?vs=14863=14952#toc

REPOSITORY
  R244 KCoreAddons

CHANGES SINCE LAST UPDATE
  https://phabricator.kde.org/D5966?vs=14863=14952

REVISION DETAIL
  https://phabricator.kde.org/D5966

AFFECTED FILES
  autotests/krandomtest.cpp
  src/lib/randomness/krandom.cpp

To: tfry, dfaure
Cc: mpyne, tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[Michael Pyne]

mpyne added a comment.


  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.

INLINE COMMENTS

> krandom.cpp:46
>  unsigned int seed;
> -init = true;
> +initialized_threads.setLocalData(true);;
>  QFile urandom(QStringLiteral("/dev/urandom"));

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

REPOSITORY
  R244 KCoreAddons

REVISION DETAIL
  https://phabricator.kde.org/D5966

To: tfry, dfaure
Cc: mpyne, tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[Thomas Friedrichsmeier]

tfry updated this revision to Diff 14863.
tfry added a comment.


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

REPOSITORY
  R244 KCoreAddons

CHANGES SINCE LAST UPDATE
  https://phabricator.kde.org/D5966?vs=14831=14863

BRANCH
  master

REVISION DETAIL
  https://phabricator.kde.org/D5966

AFFECTED FILES
  autotests/krandomtest.cpp
  src/lib/randomness/krandom.cpp

To: tfry, dfaure
Cc: mpyne, tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[Thomas Friedrichsmeier]

tfry added a comment.


  In https://phabricator.kde.org/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.

REPOSITORY
  R244 KCoreAddons

REVISION DETAIL
  https://phabricator.kde.org/D5966

To: tfry, dfaure
Cc: mpyne, tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[René J . V . Bertin]

rjvbb added a comment.


  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?

REPOSITORY
  R244 KCoreAddons

REVISION DETAIL
  https://phabricator.kde.org/D5966

To: tfry, dfaure
Cc: mpyne, tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[Michael Pyne]

mpyne added a comment.


  Would it be better to use `QThreadStorage` (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.

REPOSITORY
  R244 KCoreAddons

REVISION DETAIL
  https://phabricator.kde.org/D5966

To: tfry, dfaure
Cc: mpyne, tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[Thomas Friedrichsmeier]

tfry updated this revision to Diff 14831.
tfry added a comment.


  Ensure proper per-thread random-seeding in KRandom::random().
  
  As commented, the problem is somewhat different, than I though, 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 
https://phabricator.kde.org/R244: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.

REPOSITORY
  R244 KCoreAddons

CHANGES SINCE LAST UPDATE
  https://phabricator.kde.org/D5966?vs=14824=14831

BRANCH
  master

REVISION DETAIL
  https://phabricator.kde.org/D5966

AFFECTED FILES
  src/lib/randomness/krandom.cpp

To: tfry, dfaure
Cc: tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[René J . V . Bertin]

rjvbb added a comment.


  I was going to reflect that it would be better to set `init` in an atomic 
operation, but:
  
  In https://phabricator.kde.org/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?
  
  Or a simple QSet containing the thread ID, whichever is cheapest?

REPOSITORY
  R244 KCoreAddons

REVISION DETAIL
  https://phabricator.kde.org/D5966

To: tfry, dfaure
Cc: tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[Thomas Friedrichsmeier]

tfry added a comment.


  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?

REPOSITORY
  R244 KCoreAddons

REVISION DETAIL
  https://phabricator.kde.org/D5966

To: tfry, dfaure
Cc: tfry, rjvbb, #frameworks

D5966: Fix race-condition in KRandom-seeding.

[Thomas Friedrichsmeier]

tfry created this revision.
Restricted Application added a project: Frameworks.
Restricted Application added a subscriber: Frameworks.

REVISION 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.

REPOSITORY
  R244 KCoreAddons

BRANCH
  master

REVISION DETAIL
  https://phabricator.kde.org/D5966

AFFECTED FILES
  src/lib/randomness/krandom.cpp

To: tfry, dfaure
Cc: tfry, rjvbb, #frameworks