random is not multithread-safe in Cygwin

random is not multithread-safe in Cygwin

[Bruno Haible]

[-- Attachment #1: Type: text/plain, Size: 856 bytes --]

The function 'random' is, unlike 'rand', not marked as not MT-safe in POSIX
[1][2]. Thus it must be multithread-safe [3]:
  "Each function defined in the System Interfaces volume of POSIX.1-2017
   is thread-safe unless explicitly stated otherwise."

And indeed glibc, musl libc, AIX, Android, and even NetBSD implement it in a
multithread-safe way.

On Cygwin 2.9.0 and 3.4.6, it is not multithread-safe.

How to reproduce:
1. Compile the attached program.
   $ x86_64-pc-cygwin-gcc foo.c
2. Run it.
   $ ./a.exe
Expected: No output.
Actual: Output such as
  Expected value #367 not found in multithreaded results.

[1] https://pubs.opengroup.org/onlinepubs/9699919799/functions/initstate.html
[2] https://pubs.opengroup.org/onlinepubs/9699919799/functions/rand.html
[3] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap03.html#tag_03_407

[-- Attachment #2: foo.c --]
[-- Type: text/x-csrc, Size: 4391 bytes --]

/* Multithread-safety test for random().
   Copyright (C) 2023 Free Software Foundation, Inc.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */

/* Written by Bruno Haible <bruno@clisp.org>, 2023.  */

/* Whether to help the scheduler through explicit yield().
   Uncomment this to see if the operating system has a fair scheduler.  */
#define EXPLICIT_YIELD 1

/* Number of simultaneous threads.  */
#define THREAD_COUNT 4

/* Number of random() invocations operations performed in each thread.
   This value is chosen so that the unit test terminates quickly.
   To reliably determine whether a random() implementation is multithread-safe,
   set REPEAT_COUNT to 1000000 and run the test 100 times:
     $ for i in `seq 100`; do ./test-random-mt; done
 */
#define REPEAT_COUNT 1000000

/* Specification.  */
#include <stdlib.h>

#include <assert.h>
#include <pthread.h>
#include <stdio.h>

#if EXPLICIT_YIELD
# include <sched.h>
# define yield() sched_yield ()
#else
# define yield()
#endif

/* This test runs REPEAT_COUNT invocations of random() in each thread and stores
   the result, then compares the first REPEAT_COUNT among these
     THREAD_COUNT * REPEAT_COUNT
   random numbers against a precomputed sequence with the same seed.  */

static void *
random_invocator_thread (void *arg)
{
  long *storage = (long *) arg;
  int repeat;

  for (repeat = 0; repeat < REPEAT_COUNT; repeat++)
    {
      storage[repeat] = random ();
      yield ();
    }

  return NULL;
}

int
main ()
{
  unsigned int seed = 19891109;

  /* First, get the expected sequence of random() results.  */
  srandom (seed);
  long *expected = (long *) malloc (REPEAT_COUNT * sizeof (long));
  assert (expected != NULL);
  {
    int repeat;
    for (repeat = 0; repeat < REPEAT_COUNT; repeat++)
      expected[repeat] = random ();
  }

  /* Then, run REPEAT_COUNT invocations of random() each, in THREAD_COUNT
     separate threads.  */
  pthread_t threads[THREAD_COUNT];
  long *thread_results[THREAD_COUNT];
  srandom (seed);
  {
    int i;
    for (i = 0; i < THREAD_COUNT; i++)
      {
        thread_results[i] = (long *) malloc (REPEAT_COUNT * sizeof (long));
        assert (thread_results[i] != NULL);
      }
    for (i = 0; i < THREAD_COUNT; i++)
      assert (pthread_create (&threads[i], NULL, random_invocator_thread, thread_results[i]) == 0);
  }

  /* Wait for the threads to terminate.  */
  {
    int i;
    for (i = 0; i < THREAD_COUNT; i++)
      assert (pthread_join (threads[i], NULL) == 0);
  }

  /* Finally, determine whether the threads produced the same sequence of
     random() results.  */
  {
    int expected_index;
    int result_index[THREAD_COUNT];
    int i;

    for (i = 0; i < THREAD_COUNT; i++)
      result_index[i] = 0;

    for (expected_index = 0; expected_index < REPEAT_COUNT; expected_index++)
      {
        long expected_value = expected[expected_index];

        for (i = 0; i < THREAD_COUNT; i++)
          {
            if (thread_results[i][result_index[i]] == expected_value)
              {
                result_index[i]++;
                break;
              }
          }
        if (i == THREAD_COUNT)
          {
            if (expected_index == 0)
              {
                /* This occurs on platforms like OpenBSD, where srandom() has no
                   effect and random() always return non-deterministic values.
                   Mark the test as SKIP.  */
                fprintf (stderr, "Skipping test: random() is non-deterministic.\n");
                return 77;
              }
            else
              {
                fprintf (stderr, "Expected value #%d not found in multithreaded results.\n",
                         expected_index);
                return 1;
              }
          }
      }
  }

  return 0;
}

Re: random is not multithread-safe in Cygwin

[Corinna Vinschen]

Hi Bruno,

On Nov 10 17:19, Bruno Haible via Cygwin wrote:
> The function 'random' is, unlike 'rand', not marked as not MT-safe in POSIX
> [1][2]. Thus it must be multithread-safe [3]:
>   "Each function defined in the System Interfaces volume of POSIX.1-2017
>    is thread-safe unless explicitly stated otherwise."
> 
> And indeed glibc, musl libc, AIX, Android, and even NetBSD implement it in a
> multithread-safe way.

Our code is from FreeBSD, originally.  I checked the latest code from
FreeBSD.  It doesn't lock anything in random() and generates the same
error when running the same test app.

Why is that ok for FreeBSD?


Corinna




> 
> On Cygwin 2.9.0 and 3.4.6, it is not multithread-safe.
> 
> How to reproduce:
> 1. Compile the attached program.
>    $ x86_64-pc-cygwin-gcc foo.c
> 2. Run it.
>    $ ./a.exe
> Expected: No output.
> Actual: Output such as
>   Expected value #367 not found in multithreaded results.
> 
> [1] https://pubs.opengroup.org/onlinepubs/9699919799/functions/initstate.html
> [2] https://pubs.opengroup.org/onlinepubs/9699919799/functions/rand.html
> [3] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap03.html#tag_03_407

> /* Multithread-safety test for random().
>    Copyright (C) 2023 Free Software Foundation, Inc.
> 
>    This program is free software: you can redistribute it and/or modify
>    it under the terms of the GNU General Public License as published by
>    the Free Software Foundation, either version 3 of the License, or
>    (at your option) any later version.
> 
>    This program is distributed in the hope that it will be useful,
>    but WITHOUT ANY WARRANTY; without even the implied warranty of
>    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
>    GNU General Public License for more details.
> 
>    You should have received a copy of the GNU General Public License
>    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
> 
> /* Written by Bruno Haible <bruno@clisp.org>, 2023.  */
> 
> /* Whether to help the scheduler through explicit yield().
>    Uncomment this to see if the operating system has a fair scheduler.  */
> #define EXPLICIT_YIELD 1
> 
> /* Number of simultaneous threads.  */
> #define THREAD_COUNT 4
> 
> /* Number of random() invocations operations performed in each thread.
>    This value is chosen so that the unit test terminates quickly.
>    To reliably determine whether a random() implementation is multithread-safe,
>    set REPEAT_COUNT to 1000000 and run the test 100 times:
>      $ for i in `seq 100`; do ./test-random-mt; done
>  */
> #define REPEAT_COUNT 1000000
> 
> /* Specification.  */
> #include <stdlib.h>
> 
> #include <assert.h>
> #include <pthread.h>
> #include <stdio.h>
> 
> #if EXPLICIT_YIELD
> # include <sched.h>
> # define yield() sched_yield ()
> #else
> # define yield()
> #endif
> 
> /* This test runs REPEAT_COUNT invocations of random() in each thread and stores
>    the result, then compares the first REPEAT_COUNT among these
>      THREAD_COUNT * REPEAT_COUNT
>    random numbers against a precomputed sequence with the same seed.  */
> 
> static void *
> random_invocator_thread (void *arg)
> {
>   long *storage = (long *) arg;
>   int repeat;
> 
>   for (repeat = 0; repeat < REPEAT_COUNT; repeat++)
>     {
>       storage[repeat] = random ();
>       yield ();
>     }
> 
>   return NULL;
> }
> 
> int
> main ()
> {
>   unsigned int seed = 19891109;
> 
>   /* First, get the expected sequence of random() results.  */
>   srandom (seed);
>   long *expected = (long *) malloc (REPEAT_COUNT * sizeof (long));
>   assert (expected != NULL);
>   {
>     int repeat;
>     for (repeat = 0; repeat < REPEAT_COUNT; repeat++)
>       expected[repeat] = random ();
>   }
> 
>   /* Then, run REPEAT_COUNT invocations of random() each, in THREAD_COUNT
>      separate threads.  */
>   pthread_t threads[THREAD_COUNT];
>   long *thread_results[THREAD_COUNT];
>   srandom (seed);
>   {
>     int i;
>     for (i = 0; i < THREAD_COUNT; i++)
>       {
>         thread_results[i] = (long *) malloc (REPEAT_COUNT * sizeof (long));
>         assert (thread_results[i] != NULL);
>       }
>     for (i = 0; i < THREAD_COUNT; i++)
>       assert (pthread_create (&threads[i], NULL, random_invocator_thread, thread_results[i]) == 0);
>   }
> 
>   /* Wait for the threads to terminate.  */
>   {
>     int i;
>     for (i = 0; i < THREAD_COUNT; i++)
>       assert (pthread_join (threads[i], NULL) == 0);
>   }
> 
>   /* Finally, determine whether the threads produced the same sequence of
>      random() results.  */
>   {
>     int expected_index;
>     int result_index[THREAD_COUNT];
>     int i;
> 
>     for (i = 0; i < THREAD_COUNT; i++)
>       result_index[i] = 0;
> 
>     for (expected_index = 0; expected_index < REPEAT_COUNT; expected_index++)
>       {
>         long expected_value = expected[expected_index];
> 
>         for (i = 0; i < THREAD_COUNT; i++)
>           {
>             if (thread_results[i][result_index[i]] == expected_value)
>               {
>                 result_index[i]++;
>                 break;
>               }
>           }
>         if (i == THREAD_COUNT)
>           {
>             if (expected_index == 0)
>               {
>                 /* This occurs on platforms like OpenBSD, where srandom() has no
>                    effect and random() always return non-deterministic values.
>                    Mark the test as SKIP.  */
>                 fprintf (stderr, "Skipping test: random() is non-deterministic.\n");
>                 return 77;
>               }
>             else
>               {
>                 fprintf (stderr, "Expected value #%d not found in multithreaded results.\n",
>                          expected_index);
>                 return 1;
>               }
>           }
>       }
>   }
> 
>   return 0;
> }

> 
> -- 
> Problem reports:      https://cygwin.com/problems.html
> FAQ:                  https://cygwin.com/faq/
> Documentation:        https://cygwin.com/docs.html
> Unsubscribe info:     https://cygwin.com/ml/#unsubscribe-simple

Re: random is not multithread-safe in Cygwin

[Brian Inglis]

On 2023-11-13 09:12, Corinna Vinschen via Cygwin wrote:
> On Nov 10 17:19, Bruno Haible via Cygwin wrote:
>> The function 'random' is, unlike 'rand', not marked as not MT-safe in POSIX
>> [1][2]. Thus it must be multithread-safe [3]:
>>    "Each function defined in the System Interfaces volume of POSIX.1-2017
>>     is thread-safe unless explicitly stated otherwise."
>> And indeed glibc, musl libc, AIX, Android, and even NetBSD implement it in a
>> multithread-safe way.

> Our code is from FreeBSD, originally. I checked the latest code from
> FreeBSD. It doesn't lock anything in random() and generates the same
> error when running the same test app.
> Why is that ok for FreeBSD?

It appears that random(3) is intended to provide a single random series during 
execution of a program with simple needs; behaviour is not reproducible when 
threaded, says POSIX, newlib, and Linux (below).

 From POSIX The Open Group Base Specifications Issue 7, 2018 edition IEEE Std 
1003.1-2017 Volume 2: System Interfaces and initstate(3p) to which random(3p) 
refers and defers but does not link or .so:

"NAME
        random — generate pseudo‐random number

SYNOPSIS
        #include <stdlib.h>

        long random(void);

DESCRIPTION
        Refer to initstate()."

* That's all folks!

"NAME
	initstate, random, setstate, srandom - pseudo-random number functions
...
APPLICATION USAGE
...
Threaded applications should use erand48(), nrand48(), or jrand48() instead of 
random() when an independent random number sequence in multiple threads is 
required."

 From newlib:

"NAME
        random, srandom - pseudo-random numbers
...
NOTES
        random and srandom are unsafe for multi-threaded applications.

        _XOPEN_SOURCE may be any value >= 500.

PORTABILITY
        random is required by XSI. This implementation uses the same algorithm 
as rand."

* Newlib, and presumably FreeBSD, do not support initstate, setstate, or > 8 
(for amd64/x86_64) bytes state.

 From man-pages-linux random(3):

"CAVEATS
...
        The random() function should not be used in multithreaded programs where 
reproducible behavior is required.
        Use random_r(3) for that purpose."

* As usual, random_r(3) requires the caller to provide an initialized state 
vector buffer (of 8-256 bytes), allowing the caller to decide the amount of 
randomness and scope of the random series, and possibly call initstate_r(3), to 
control the seed.

-- 
Take care. Thanks, Brian Inglis              Calgary, Alberta, Canada

La perfection est atteinte                   Perfection is achieved
non pas lorsqu'il n'y a plus rien à ajouter  not when there is no more to add
mais lorsqu'il n'y a plus rien à retirer     but when there is no more to cut
                                 -- Antoine de Saint-Exupéry

Re: random is not multithread-safe in Cygwin

[Bruno Haible]

Corinna Vinschen wrote:
> > And indeed glibc, musl libc, AIX, Android, and even NetBSD implement it in a
> > multithread-safe way.
> 
> Our code is from FreeBSD, originally.  I checked the latest code from
> FreeBSD.  It doesn't lock anything in random() and generates the same
> error when running the same test app.
> 
> Why is that ok for FreeBSD?

It is not OK in FreeBSD, either. This is what I noted in the Gnulib manual:
https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=blob;f=doc/posix-functions/random.texi

But it is MT-safe in NetBSD (in the '#ifndef SMALL_RANDOM' branch):
http://cvsweb.netbsd.org/bsdweb.cgi/src/common/lib/libc/stdlib/random.c?rev=1.7&content-type=text/x-cvsweb-markup

Bruno

Re: random is not multithread-safe in Cygwin

[Corinna Vinschen]

On Nov 13 19:04, Bruno Haible via Cygwin wrote:
> Corinna Vinschen wrote:
> > > And indeed glibc, musl libc, AIX, Android, and even NetBSD implement it in a
> > > multithread-safe way.
> > 
> > Our code is from FreeBSD, originally.  I checked the latest code from
> > FreeBSD.  It doesn't lock anything in random() and generates the same
> > error when running the same test app.
> > 
> > Why is that ok for FreeBSD?
> 
> It is not OK in FreeBSD, either. This is what I noted in the Gnulib manual:
> https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=blob;f=doc/posix-functions/random.texi
> 
> But it is MT-safe in NetBSD (in the '#ifndef SMALL_RANDOM' branch):
> http://cvsweb.netbsd.org/bsdweb.cgi/src/common/lib/libc/stdlib/random.c?rev=1.7&content-type=text/x-cvsweb-markup

Ok, I pushed a patch(*) to make the random(3) functions thread-safe, more
or less following NetBSDs lead.  If you get a chance, give the next test
release cygwin-3.5.0-0.459.gd223f095905a a try.

The patch will be part of the next release, 3.4.10.


Thanks,
Corinna

(*) https://sourceware.org/git/?p=newlib-cygwin.git;a=commit;h=06e463223b95