Skip to content

Threadsafe protection against zero state of xoshiro128ss

Sergey Larin requested to merge sergy.larin/fpcsrc:xoshiro128-threadsafe into main

When using random from multiple threads, it may happen that all elements of state are equal to 0, which is not valid for Xoshiro128ss.

The problem is that storing into state[0], state[1], state[2], state[3] is not an atomic operation.
Accordingly, the completely correct solution to the problem is to use an atomic store of 16 bytes.
But, firstly, this is not a fast operation on cpu64, and secondly, such an operation is absent in cpu32.
Also, the solution is to use some other RNG instead of Xoshiro128ss, which has a 64-bit state, but this is not the subject of this MR...

Below is an example of how you can get an invalid state, after which Xoshiro128ss_32.Next will always return only 0.

XoshiroThreadsafeBugTest
program XoshiroThreadsafeBugTest;

{$mode objfpc}

uses
  Classes;

var
  RandSeed : Cardinal;

var
  OldRandSeed : Cardinal = Cardinal(not Cardinal(0));

type
  SplitMix64 = object
    procedure Setup(const seed: uint64); inline;
    function Next: uint64;
  private
    state: uint64;
  end;

procedure SplitMix64.Setup(const seed: uint64);
begin
  state := seed;
end;

function SplitMix64.Next: uint64;
var
  z: uint64;
begin
  z := state + $9e3779b97f4a7c15;
  state := z;
  z := (z xor (z shr 30)) * $bf58476d1ce4e5b9;
  z := (z xor (z shr 27)) * $94d049bb133111eb;
  result := z xor (z shr 31);
end;

type
  Xoshiro128ss_32 = object
    procedure Setup(const seed: uint64);
    function Next: uint32;
  private
    state: array[0 .. 3] of uint32;
  end;

  procedure Xoshiro128ss_32.Setup(const seed: uint64);
  var
    sm: SplitMix64;
    x: uint64;
  begin
    sm.Setup(seed);
    x := sm.Next;
    state[0] := Lo(x); state[1] := Hi(x);
    x := sm.Next;
    state[2] := Lo(x); state[3] := Hi(x);
  end;

var
  BUGFIX: Boolean = false;
threadvar
  T1: Boolean;

  function Xoshiro128ss_32.Next: uint32;
  var
    s0, s1, s2, s3: uint32;
  begin
    s0 := state[0];
    s1 := state[1];
    s2 := state[2];
    s3 := state[3];
  {$ifdef FPC_HAS_FEATURE_THREADING}
  if BUGFIX then
    if s0 or s1 or s2 or s3 = 0 then
      s0 := 1;
  {$endif}
    s2 := s2 xor s0;
    s3 := s3 xor s1;
    result := RolDWord(s1 * 5, 7) * 9;

    state[0] := s0 xor s3;

  if T1 then
    TThread.Sleep(2000);

    state[1] := s1 xor s2;
    state[2] := s2 xor (s1 shl 9);
    state[3] := RolDWord(s3, 11);
  end;

var
  GlobalXsr128_32: Xoshiro128ss_32 = (state: ($AFF181C0, $73B13BA2, $1340D3B4, $61204305));

  procedure ReseedGlobalRNG;
  begin
    GlobalXsr128_32.Setup(RandSeed);
    RandSeed := not RandSeed;
    OldRandSeed := RandSeed;
  end;

  function xsr128_32_u32rand: uint32;
  begin
    if RandSeed <> OldRandSeed then ReseedGlobalRNG;
    result := GlobalXsr128_32.Next;
  end;


procedure TreadProc1;
begin
  T1 := True;
  xsr128_32_u32rand;
end;

var
  Thread1: TThread;
  R1, R2, R3, R4: uint32;
begin
  //BUGFIX := true; // <-- !!!

  //RandSeed := X;
  GlobalXsr128_32.state[0] := high(uint32);
  GlobalXsr128_32.state[1] := 0;
  GlobalXsr128_32.state[2] := high(uint32);
  GlobalXsr128_32.state[3] := 0;
  OldRandSeed := RandSeed;

  Thread1 := TThread.CreateAnonymousThread(@TreadProc1);
  Thread1.FreeOnTerminate := False;
  Thread1.Start;

  TThread.Sleep(1000);

  //RandSeed := X;
  GlobalXsr128_32.state[0] := high(uint32);
  GlobalXsr128_32.state[1] := 0;
  GlobalXsr128_32.state[2] := high(uint32);
  GlobalXsr128_32.state[3] := 0;
  OldRandSeed := RandSeed;
  xsr128_32_u32rand;
  xsr128_32_u32rand;
  xsr128_32_u32rand;

  Thread1.WaitFor;
  Thread1.Free;

  with GlobalXsr128_32 do
    if (state[0] = 0) and (state[1] = 0) and (state[2] = 0) and (state[3] = 0) then
    begin
      R1 := xsr128_32_u32rand;
      R2 := xsr128_32_u32rand;
      R3 := xsr128_32_u32rand;
      R4 := xsr128_32_u32rand;
      // ...
      WriteLn('R1: ', R1);
      WriteLn('R2: ', R2);
      WriteLn('R3: ', R3);
      WriteLn('R4: ', R4);
      if (R1 = R2) and (R2 = R3) and (R3 = R4) then
        Halt(1); // BUG
    end;
end.

A workaround and simple solution to the problem is after reading state into local variables, check s0, s1, s2, s3 and if all are equal to 0, then fix this, for example, by setting s0 to 1.

Related to #38237 (closed)

Edited by Sergey Larin

Merge request reports