Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

[Bruno Haible]

Noel Grandin wrote in cygwin-patches:
> Pardon my ignorance, but why not rather use the Windows SRWLock functionality?
> https://learn.microsoft.com/en-us/windows/win32/sync/slim-reader-writer--srw--locks
> 
> SRW locks are very fast, only require a single pointer-sized storage area, can be statically initialised, and do not 
> need to be destroyed, so there is no possibibilty of memory leakage.
> 
> Then the implementation simply becomes
> 
> int pthread::once (pthread_once_t *once_control, void (*init_routine) (void))
> {
>      AcquireSRWLockExclusive(once_control->lock);
>      if (!once_control->state)
>      {
>          init_routine()
>          once_control->state = 1;
>      }
>      ReleaseSRWLockExclusive(once_control->lock);
> }

SRW locks are spin-locks. Since they are only pointer-sized,
ReleaseSRWLockExclusive cannot notify other threads — unlike CRITICAL_SECTION.
Therefore, AcquireSRWLockExclusive must busy-loop when the lock is already
held.

But busy-looping is a bad practice for pthread_once. In the case,
for example, that the init_routine reads a multi-megabyte data
structure into memory and parses it, the other threads that wait
on the result of this operation would by busy-looping, eating
full CPU time.

Bruno

Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

[Noel Grandin]

On 5/30/2024 10:47 AM, Bruno Haible wrote:
> 
> SRW locks are spin-locks. Since they are only pointer-sized,
> ReleaseSRWLockExclusive cannot notify other threads — unlike CRITICAL_SECTION.
> Therefore, AcquireSRWLockExclusive must busy-loop when the lock is already
> held.
> 

No, they only spin briefly, before calling into the OS to sleep - see the article about their internals here:

https://learn.microsoft.com/en-us/archive/msdn-magazine/2012/november/windows-with-c-the-evolution-of-synchronization-in-windows-and-c#slim-readerwriter-lock


Alternatively, Windows already has an API for init-once i.e.
   https://learn.microsoft.com/en-us/windows/win32/sync/one-time-initialization

Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

[Bruno Haible]

Noel Grandin wrote:
> > SRW locks are spin-locks. Since they are only pointer-sized,
> > ReleaseSRWLockExclusive cannot notify other threads — unlike CRITICAL_SECTION.
> > Therefore, AcquireSRWLockExclusive must busy-loop when the lock is already
> > held.
> > 
> 
> No, they only spin briefly, before calling into the OS to sleep - see the article about their internals here:
> 
> https://learn.microsoft.com/en-us/archive/msdn-magazine/2012/november/windows-with-c-the-evolution-of-synchronization-in-windows-and-c#slim-readerwriter-lock

Still: Does ReleaseSRWLockExclusive notify other threads?

> Alternatively, Windows already has an API for init-once i.e.
>    https://learn.microsoft.com/en-us/windows/win32/sync/one-time-initialization

Functionally, the INIT_ONCE looks interesting. But, like Takashi Yano mentioned,
how would you make it fit into a pthread_once_t that is defined as
  struct { pthread_mutex_t mutex; int state; }
?

Bruno

Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

[Noel Grandin]

On 5/30/2024 11:15 AM, Bruno Haible wrote:
> 
> Still: Does ReleaseSRWLockExclusive notify other threads?
> 

Of course? How else would a lock work, it must release other waiters?

It might not be a fair lock though, which is not a problem for this situation, which does not require fair locking.


> Functionally, the INIT_ONCE looks interesting. But, like Takashi Yano mentioned,
> how would you make it fit into a pthread_once_t that is defined as
>    struct { pthread_mutex_t mutex; int state; }
> ?

Something like:

struct once {
    union {
       pthread_mutex_t old_mutex_field_for_size_compatibility;
       SRWLOCK lock = SRWLOCK_INIT;
     };
     int state;
};

Regards, Noel Grandin

Re: SRW locks

[Bruno Haible]

Noel Grandin wrote:
> > Still: Does ReleaseSRWLockExclusive notify other threads?
> > 
> 
> Of course? How else would a lock work, it must release other waiters?
> 
> It might not be a fair lock though, which is not a problem for this situation, which does not require fair locking.
> 
> 
> > Functionally, the INIT_ONCE looks interesting. But, like Takashi Yano mentioned,
> > how would you make it fit into a pthread_once_t that is defined as
> >    struct { pthread_mutex_t mutex; int state; }
> > ?
> 
> Something like:
> 
> struct once {
>     union {
>        pthread_mutex_t old_mutex_field_for_size_compatibility;
>        SRWLOCK lock = SRWLOCK_INIT;
>      };
>      int state;
> };

Reading [1], it seems that this might indeed work, and be faster than code
that uses CRITICAL_SECTIONs.

Still, something to watch out is this bug [2].

All in all, I would say that every such change ought to be tested with a
nontrivial test program that performs several thousands of rounds.

Bruno

[1] https://marabos.nl/atomics/os-primitives.html
[2] https://old.reddit.com/r/cpp/comments/1b55686/maybe_possible_bug_in_stdshared_mutex_on_windows/

Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

[Bruno Haible]

Takashi Yano wrote in cygwin-patches:
>  int
>  pthread::once (pthread_once_t *once_control, void (*init_routine) (void))
>  {
> -  // already done ?
> -  if (once_control->state)
> +  /* Sign bit of once_control->state is used as done flag */
> +  if (once_control->state & INT_MIN)
>      return 0;
>  
> +  /* The type of &once_control->state is int *, which is compatible with
> +     LONG * (the type of the first argument of InterlockedIncrement()). */
> +  InterlockedIncrement (&once_control->state);
>    pthread_mutex_lock (&once_control->mutex);
> -  /* Here we must set a cancellation handler to unlock the mutex if needed */
> -  /* but a cancellation handler is not the right thing. We need this in the thread
> -   *cleanup routine. Assumption: a thread can only be in one pthread_once routine
> -   *at a time. Stote a mutex_t *in the pthread_structure. if that's non null unlock
> -   *on pthread_exit ();
> -   */

Sorry, in a unified diff form this is unreadable. One needs to look at the
entire function. A context diff would have been better. So:

int
pthread::once (pthread_once_t *once_control, void (*init_routine) (void))
{
  /* Sign bit of once_control->state is used as done flag */
  if (once_control->state & INT_MIN)
    return 0;

  /* The type of &once_control->state is int *, which is compatible with
     LONG * (the type of the first argument of InterlockedIncrement()). */
  InterlockedIncrement (&once_control->state);
  pthread_mutex_lock (&once_control->mutex);
  if (!(once_control->state & INT_MIN))
    {
      init_routine ();
      once_control->state |= INT_MIN;
    }
  pthread_mutex_unlock (&once_control->mutex);
  if (InterlockedDecrement (&once_control->state) == INT_MIN)
    pthread_mutex_destroy (&once_control->mutex);
  return 0;
}

1) The overall logic seems right (using bit 31 of the state word as a
'done' bit), and the last thread that used the mutex destroys it.

2) However, the 'state' field is not volatile, and therefore the memory
model does not guarantee that an assignment

     once_control->state |= INT_MIN;

done in one thread has an effect on the values seen by other threads
that do

     if (once_control->state & INT_MIN)

As long as there is no synchronization between the two CPUs that execute
the two threads, one CPU may indefinitely see the old value of
once_control->state, while the other CPU's new value is not being
"broadcasted" to all CPUs.

3) Also, as noted by Noel Grandin, there is a race: If one thread does

     once_control->state |= INT_MIN;

while another thread does

     InterlockedIncrement (&once_control->state);
or
     InterlockedDecrement (&once_control->state)

the result can be that the increment or decrement is nullified. If it's
an increment that gets nullified, the pthread_mutex_destroy occurs too
early, with fatal consequences. If it's a decrement that get nullified,
the pthread_mutex_destroy never happens, and there is therefore a resource
leak.

4) Does the test program that I posted in
<https://cygwin.com/pipermail/cygwin/2024-May/255987.html> now pass?
Notes:
  - You should set
      #define ENABLE_DEBUGGING 0
    because with the debugging output, it nearly always succeeds.
  - You should run it 10 times in a row, not just once. It may well
    succeed 9 out of 10 times and fail 1 out of 10 times.

Bruno

Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

[Bruno Haible]

Takashi Yano wrote in cygwin-patches:
> With v3 patch:
> int
> pthread::once (pthread_once_t *once_control, void (*init_routine) (void))
> {
>   /* Sign bit of once_control->state is used as done flag */
>   if (once_control->state & INT_MIN)
>     return 0;
> 
>   /* The type of &once_control->state is int *, which is compatible with
>      LONG * (the type of the first argument of InterlockedIncrement()). */
>   InterlockedIncrement (&once_control->state);
>   pthread_mutex_lock (&once_control->mutex);
>   if (!(once_control->state & INT_MIN))
>     {
>       init_routine ();
>       InterlockedOr (&once_control->state, INT_MIN);
>     }
>   pthread_mutex_unlock (&once_control->mutex);
>   if (InterlockedDecrement (&once_control->state) == INT_MIN)
>     pthread_mutex_destroy (&once_control->mutex);
>   return 0;
> }

Looks good to me.

If it passes 10 or 100 runs of my test program from
<https://cygwin.com/pipermail/cygwin/2024-May/255987.html>,
I would say, it's good.

Thanks!

Bruno

Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

[Bruno Haible]

Hi Takashi Yano,

> With v3 patch:
> int
> pthread::once (pthread_once_t *once_control, void (*init_routine) (void))
> {
>   /* Sign bit of once_control->state is used as done flag */
>   if (once_control->state & INT_MIN)
>     return 0;
> 
    // HERE: Point A.

>   /* The type of &once_control->state is int *, which is compatible with
>      LONG * (the type of the first argument of InterlockedIncrement()). */
>   InterlockedIncrement (&once_control->state);
>   pthread_mutex_lock (&once_control->mutex);
>   if (!(once_control->state & INT_MIN))
>     {
>       init_routine ();
>       InterlockedOr (&once_control->state, INT_MIN);
>     }
>   pthread_mutex_unlock (&once_control->mutex);
>   if (InterlockedDecrement (&once_control->state) == INT_MIN)

      // HERE: Point B.

>     pthread_mutex_destroy (&once_control->mutex);

      // HERE: Point C.

>   return 0;
> }

I said "looks good to me", but unfortunately I have to withdraw this.
The code to which I pointed you had two race conditions, unfortunately,
and this code (v3) has the same two race conditions:

(1) It can happen that the pthread_mutex_destroy is executed twice, which is
    undefined behaviour.

                 thread1                      thread2
                 -------                      -------

                 Runs upto A.                 Runs upto A.

                 Runs upto B:
                 sets state to 1,
                 locks,
                 sets state to INT_MIN + 1,
                 unlocks,
                 sets state to INT_MIN.

                                              Runs upto B:
                                              sets state to INT_MIN + 1,
                                              locks,
                                              unlocks,
                                              sets state to INT_MIN.

                 calls pthread_mutex_destroy

                                              calls pthread_mutex_destroy

(2) It can happen that pthread_mutex_lock is executed on a mutex that is
    already destroyed, which is undefined behaviour.

                 thread1                      thread2
                 -------                      -------

                 Runs upto A.                 Runs upto A.

                 Runs upto C:
                 sets state to 1,
                 locks,
                 sets state to INT_MIN + 1,
                 unlocks,
                 sets state to INT_MIN,
                 calls pthread_mutex_destroy

                                              Attempts to run upto B:
                                              sets state to INT_MIN + 1,
                                              locks  -> BOOM, SIGSEGV

A corrected implementation (that passes 100 runs of the test program)
is in
https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=blob;f=lib/pthread-once.c;h=4b4a18d2afbb915f8f97ac3ff981f519acaa5996;hb=HEAD#l41

The fix for race (1) is to extend the "done" part of the state to 2 bits
instead of just 1 bit, and to use this extra bit to ensure that only one
of the threads proceeds from B to C.

The fix for race (2) is to increment num_threads *before* testing the
'done' word and, accordingly, to decrement num_threads also when 'done'
was zero.

You should be able to transpose the logic accordingly, by using the
bit mask 0xC0000000 for the 'done' part and the bit mask 0x3FFFFFFF for
the 'num_threads' part.

Bruno

Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

[Takashi Yano]

Hi Bruno,

On Fri, 31 May 2024 16:01:35 +0200
Bruno Haible wrote:
> Hi Takashi Yano,
> 
> > With v3 patch:
> > int
> > pthread::once (pthread_once_t *once_control, void (*init_routine) (void))
> > {
> >   /* Sign bit of once_control->state is used as done flag */
> >   if (once_control->state & INT_MIN)
> >     return 0;
> > 
>     // HERE: Point A.
> 
> >   /* The type of &once_control->state is int *, which is compatible with
> >      LONG * (the type of the first argument of InterlockedIncrement()). */
> >   InterlockedIncrement (&once_control->state);
> >   pthread_mutex_lock (&once_control->mutex);
> >   if (!(once_control->state & INT_MIN))
> >     {
> >       init_routine ();
> >       InterlockedOr (&once_control->state, INT_MIN);
> >     }
> >   pthread_mutex_unlock (&once_control->mutex);
> >   if (InterlockedDecrement (&once_control->state) == INT_MIN)
> 
>       // HERE: Point B.
> 
> >     pthread_mutex_destroy (&once_control->mutex);
> 
>       // HERE: Point C.
> 
> >   return 0;
> > }
> 
> I said "looks good to me", but unfortunately I have to withdraw this.
> The code to which I pointed you had two race conditions, unfortunately,
> and this code (v3) has the same two race conditions:
> 
> (1) It can happen that the pthread_mutex_destroy is executed twice, which is
>     undefined behaviour.
> 
>                  thread1                      thread2
>                  -------                      -------
> 
>                  Runs upto A.                 Runs upto A.
> 
>                  Runs upto B:
>                  sets state to 1,
>                  locks,
>                  sets state to INT_MIN + 1,
>                  unlocks,
>                  sets state to INT_MIN.
> 
>                                               Runs upto B:
>                                               sets state to INT_MIN + 1,
>                                               locks,
>                                               unlocks,
>                                               sets state to INT_MIN.
> 
>                  calls pthread_mutex_destroy
> 
>                                               calls pthread_mutex_destroy
> 
> (2) It can happen that pthread_mutex_lock is executed on a mutex that is
>     already destroyed, which is undefined behaviour.
> 
>                  thread1                      thread2
>                  -------                      -------
> 
>                  Runs upto A.                 Runs upto A.
> 
>                  Runs upto C:
>                  sets state to 1,
>                  locks,
>                  sets state to INT_MIN + 1,
>                  unlocks,
>                  sets state to INT_MIN,
>                  calls pthread_mutex_destroy
> 
>                                               Attempts to run upto B:
>                                               sets state to INT_MIN + 1,
>                                               locks  -> BOOM, SIGSEGV

I reconsidered how it can be fixed before reading the following your
idea for double-check. The result is as follows (submitted as v4 patch).

int
pthread::once (pthread_once_t *once_control, void (*init_routine) (void))
{
  /* Sign bit of once_control->state is used as done flag.
     Similary, the next significant bit is used as destroyed flag. */
  const int done = INT_MIN;		/* 0b1000000000000000 */
  const int destroyed = INT_MIN >> 1;	/* 0b1100000000000000 */
  if (once_control->state & done)
    return 0;

  /* The type of &once_control->state is int *, which is compatible with
     LONG * (the type of the pointer argument of InterlockedXxx()). */
  if ((InterlockedIncrement (&once_control->state) & done) == 0)
    {
      pthread_mutex_lock (&once_control->mutex);
      if (!(once_control->state & done))
	{
	  init_routine ();
	  InterlockedOr (&once_control->state, done);
	}
      pthread_mutex_unlock (&once_control->mutex);
    }
  InterlockedDecrement (&once_control->state);
  if (InterlockedCompareExchange (&once_control->state,
				  destroyed, done) == done)
    pthread_mutex_destroy (&once_control->mutex);
  return 0;
}

Then, I read your idea below:

> A corrected implementation (that passes 100 runs of the test program)
> is in
> https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=blob;f=lib/pthread-once.c;h=4b4a18d2afbb915f8f97ac3ff981f519acaa5996;hb=HEAD#l41
> 
> The fix for race (1) is to extend the "done" part of the state to 2 bits
> instead of just 1 bit, and to use this extra bit to ensure that only one
> of the threads proceeds from B to C.
> 
> The fix for race (2) is to increment num_threads *before* testing the
> 'done' word and, accordingly, to decrement num_threads also when 'done'
> was zero.
> 
> You should be able to transpose the logic accordingly, by using the
> bit mask 0xC0000000 for the 'done' part and the bit mask 0x3FFFFFFF for
> the 'num_threads' part.

I believe both codes are equivalent. Could you please check?

-- 
Takashi Yano <takashi.yano@nifty.ne.jp>

Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

[Ken Brown]

Hi Takashi,

On 6/1/2024 10:18 AM, Takashi Yano via Cygwin wrote:
> int
> pthread::once (pthread_once_t *once_control, void (*init_routine) (void))
> {
>    /* Sign bit of once_control->state is used as done flag.
>       Similary, the next significant bit is used as destroyed flag. */

         Typo: Similarly

>    const int done = INT_MIN;		/* 0b1000000000000000 */
>    const int destroyed = INT_MIN >> 1;	/* 0b1100000000000000 */

Shouldn't the constants in the comments have 32 bits?  Other than that, 
LGTM.  (But you should wait for Bruno to confirm before you commit.)

Ken

Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

[Takashi Yano]

On Sat, 1 Jun 2024 12:08:51 -0400
Ken Brown wrote:
> Hi Takashi,
> 
> On 6/1/2024 10:18 AM, Takashi Yano via Cygwin wrote:
> > int
> > pthread::once (pthread_once_t *once_control, void (*init_routine) (void))
> > {
> >    /* Sign bit of once_control->state is used as done flag.
> >       Similary, the next significant bit is used as destroyed flag. */
> 
>          Typo: Similarly
> 
> >    const int done = INT_MIN;		/* 0b1000000000000000 */
> >    const int destroyed = INT_MIN >> 1;	/* 0b1100000000000000 */
> 
> Shouldn't the constants in the comments have 32 bits?  Other than that, 
> LGTM.  (But you should wait for Bruno to confirm before you commit.)

Thanks for checking!

-- 
Takashi Yano <takashi.yano@nifty.ne.jp>

Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

[Bruno Haible]

Hi Takashi Yano,

> The result is as follows (submitted as v4 patch).
> 
> int
> pthread::once (pthread_once_t *once_control, void (*init_routine) (void))
> {
>   /* Sign bit of once_control->state is used as done flag.
>      Similary, the next significant bit is used as destroyed flag. */
>   const int done = INT_MIN;		/* 0b1000000000000000 */
>   const int destroyed = INT_MIN >> 1;	/* 0b1100000000000000 */
>   if (once_control->state & done)
>     return 0;
> 
>   /* The type of &once_control->state is int *, which is compatible with
>      LONG * (the type of the pointer argument of InterlockedXxx()). */
>   if ((InterlockedIncrement (&once_control->state) & done) == 0)
>     {
>       pthread_mutex_lock (&once_control->mutex);
>       if (!(once_control->state & done))
> 	{
> 	  init_routine ();
> 	  InterlockedOr (&once_control->state, done);
> 	}
>       pthread_mutex_unlock (&once_control->mutex);
>     }
>   InterlockedDecrement (&once_control->state);
>   if (InterlockedCompareExchange (&once_control->state,
> 				  destroyed, done) == done)
>     pthread_mutex_destroy (&once_control->mutex);
>   return 0;
> }
> ...
> I believe both codes are equivalent. Could you please check?

Yes, they are equivalent. This code is free of race conditions. (Let's
hope I am not making a mistake again.)

For legibility I would write the constant values as bit masks:
  0x80000000
  0xc0000000
and - following the habit that constant integers should have names in
upper case - I would rename
  done → DONE
  destroyed → DESTROYED

Bruno

Re: [PATCH v2] Cygwin: pthread: Fix a race issue introduced by the commit 2c5433e5da82

[Takashi Yano]

On Sun, 02 Jun 2024 15:14:51 +0200
Bruno Haible wrote:
> Hi Takashi Yano,
> 
> > The result is as follows (submitted as v4 patch).
> > 
> > int
> > pthread::once (pthread_once_t *once_control, void (*init_routine) (void))
> > {
> >   /* Sign bit of once_control->state is used as done flag.
> >      Similary, the next significant bit is used as destroyed flag. */
> >   const int done = INT_MIN;		/* 0b1000000000000000 */
> >   const int destroyed = INT_MIN >> 1;	/* 0b1100000000000000 */
> >   if (once_control->state & done)
> >     return 0;
> > 
> >   /* The type of &once_control->state is int *, which is compatible with
> >      LONG * (the type of the pointer argument of InterlockedXxx()). */
> >   if ((InterlockedIncrement (&once_control->state) & done) == 0)
> >     {
> >       pthread_mutex_lock (&once_control->mutex);
> >       if (!(once_control->state & done))
> > 	{
> > 	  init_routine ();
> > 	  InterlockedOr (&once_control->state, done);
> > 	}
> >       pthread_mutex_unlock (&once_control->mutex);
> >     }
> >   InterlockedDecrement (&once_control->state);
> >   if (InterlockedCompareExchange (&once_control->state,
> > 				  destroyed, done) == done)
> >     pthread_mutex_destroy (&once_control->mutex);
> >   return 0;
> > }
> > ...
> > I believe both codes are equivalent. Could you please check?
> 
> Yes, they are equivalent. This code is free of race conditions. (Let's
> hope I am not making a mistake again.)
> 
> For legibility I would write the constant values as bit masks:
>   0x80000000
>   0xc0000000
> and - following the habit that constant integers should have names in
> upper case - I would rename
>   done → DONE
>   destroyed → DESTROYED

Thanks for checking. I'll push the patch after the modification.

-- 
Takashi Yano <takashi.yano@nifty.ne.jp>