[newlib-cygwin] Cygwin: thread: Use simple array instead of List<pthread_key>

[Takashi Yano]

https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;h=ebd92b128f62a0b3c270319487b8486abdfa405b

commit ebd92b128f62a0b3c270319487b8486abdfa405b
Author: Takashi Yano <takashi.yano@nifty.ne.jp>
Date:   Fri Apr 4 21:22:27 2025 +0900

    Cygwin: thread: Use simple array instead of List<pthread_key>
    
    Previously, List<pthread_key>, which used fast_mutex, was used for
    accessing all the valid pthread_key. This caused a deadlock when
    another pthread_key_create() is called in the destructor registered
    by the previous pthread_key_create(). This is because the
    run_all_destructors() calls the desructor via keys.for_each() where
    both for_each() and pthread_key_create() (that calls List_insert())
    attempt to acquire the lock.
    With this patch, use simple array of pthread_key instead and realize
    quasi-lock-free access to that array refering to the glibc code.
    
    Addresses: https://cygwin.com/pipermail/cygwin/2025-March/257705.html
    Fixes: 1a821390d11d ("fix race condition in List_insert")
    Reported-by: Yuyi Wang <Strawberry_Str@hotmail.com>
    Reviewed-by: Corinna Vinschen <corinna@vinschen.de>
    Signed-off-by: Takashi Yano <takashi.yano@nifty.ne.jp>

Diff:
---
 winsup/cygwin/local_includes/thread.h | 31 +++++++++++++++++++++++-------
 winsup/cygwin/thread.cc               | 36 ++++++++++++++++++++++++++++-------
 2 files changed, 53 insertions(+), 14 deletions(-)

diff --git a/winsup/cygwin/local_includes/thread.h b/winsup/cygwin/local_includes/thread.h
index b3496281e..3955609e2 100644
--- a/winsup/cygwin/local_includes/thread.h
+++ b/winsup/cygwin/local_includes/thread.h
@@ -221,13 +221,12 @@ public:
   ~pthread_key ();
   static void fixup_before_fork ()
   {
-    keys.for_each (&pthread_key::_fixup_before_fork);
+    for_each (_fixup_before_fork);
   }
 
   static void fixup_after_fork ()
   {
-    keys.fixup_after_fork ();
-    keys.for_each (&pthread_key::_fixup_after_fork);
+    for_each (_fixup_after_fork);
   }
 
   static void run_all_destructors ()
@@ -246,21 +245,39 @@ public:
     for (int i = 0; i < PTHREAD_DESTRUCTOR_ITERATIONS; ++i)
       {
 	iterate_dtors_once_more = false;
-	keys.for_each (&pthread_key::run_destructor);
+	for_each (run_destructor);
 	if (!iterate_dtors_once_more)
 	  break;
       }
   }
 
-  /* List support calls */
-  class pthread_key *next;
 private:
-  static List<pthread_key> keys;
+  int key_idx;
+  static class keys_list {
+    LONG64 seq;
+    LONG64 busy_cnt;
+    pthread_key *key;
+    static bool used (LONG64 seq1) { return (seq1 & 3) != 0; }
+    static bool ready (LONG64 seq1) { return (seq1 & 3) == 2; }
+  public:
+    keys_list () : seq (0), busy_cnt (INT64_MIN), key (NULL) {}
+    friend class pthread_key;
+  } keys[PTHREAD_KEYS_MAX];
   void _fixup_before_fork ();
   void _fixup_after_fork ();
   void (*destructor) (void *);
   void run_destructor ();
   void *fork_buf;
+  static void for_each (void (pthread_key::*callback) ()) {
+    for (size_t cnt = 0; cnt < PTHREAD_KEYS_MAX; cnt++)
+      {
+	if (!keys_list::ready (keys[cnt].seq))
+	  continue;
+	if (InterlockedIncrement64 (&keys[cnt].busy_cnt) > 0)
+	  (keys[cnt].key->*callback) ();
+	InterlockedDecrement64 (&keys[cnt].busy_cnt);
+      }
+  }
 };
 
 class pthread_attr: public verifyable_object
diff --git a/winsup/cygwin/thread.cc b/winsup/cygwin/thread.cc
index 9ee96504b..fea6079b8 100644
--- a/winsup/cygwin/thread.cc
+++ b/winsup/cygwin/thread.cc
@@ -1666,27 +1666,49 @@ pthread_rwlock::_fixup_after_fork ()
 /* pthread_key */
 /* static members */
 /* This stores pthread_key information across fork() boundaries */
-List<pthread_key> pthread_key::keys;
+pthread_key::keys_list pthread_key::keys[PTHREAD_KEYS_MAX];
 
 /* non-static members */
 
-pthread_key::pthread_key (void (*aDestructor) (void *)):verifyable_object (PTHREAD_KEY_MAGIC), destructor (aDestructor)
+pthread_key::pthread_key (void (*aDestructor) (void *)) :
+  verifyable_object (PTHREAD_KEY_MAGIC), destructor (aDestructor)
 {
   tls_index = TlsAlloc ();
   if (tls_index == TLS_OUT_OF_INDEXES)
     magic = 0;
   else
-    keys.insert (this);
+    for (size_t cnt = 0; cnt < PTHREAD_KEYS_MAX; cnt++)
+      {
+	LONG64 seq = keys[cnt].seq;
+	if (!keys_list::used (seq)
+	    && InterlockedCompareExchange64 (&keys[cnt].seq,
+					     seq + 1, seq) == seq)
+	  {
+	    keys[cnt].key = this;
+	    keys[cnt].busy_cnt = 0;
+	    key_idx = cnt;
+	    InterlockedIncrement64 (&keys[key_idx].seq);
+	    break;
+	  }
+      }
 }
 
 pthread_key::~pthread_key ()
 {
-  /* We may need to make the list code lock the list during operations
-   */
   if (magic != 0)
     {
-      keys.remove (this);
-      TlsFree (tls_index);
+      LONG64 seq = keys[key_idx].seq;
+      if (keys_list::ready (seq)
+	  && InterlockedCompareExchange64 (&keys[key_idx].seq,
+					   seq + 1, seq) == seq)
+	{
+	  while (InterlockedCompareExchange64 (&keys[key_idx].busy_cnt,
+					       INT64_MIN, 0) > 0)
+	    yield ();
+	  keys[key_idx].key = NULL;
+	  InterlockedIncrement64 (&keys[key_idx].seq);
+	  TlsFree (tls_index);
+	}
     }
 }