Re: Some experience with the igc branch

[Pip Cet]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Pip Cet <pipcet@protonmail.com> writes:
>
>> I'll spare you most of the details for now, but having read the mps
>> header, MPS allocation is not safe to use from separate threads without
>> locking the AP (or having per-thread APs), which we might end up doing
>> on Windows, IIRC.
>
> Now I'm confused. We're using thread allocation points. See
> create_thread_aps, thread_ap, and so on.

I was confused.  This is only a problem if we allocate memory from a
signal handler, which is effectively sharing the per-thread structure.

(I'm still confused. My patch worked on the first attempt, which my code
never does.  I suspect that while I made a mistake, it caused a subtle
bug rather than an obvious one.)

And we don't want to allocate memory from signal handlers, right?  We
could, now (see warnings below):

diff --git a/src/igc.c b/src/igc.c
index eb72406e529..14ecc30f982 100644
--- a/src/igc.c
+++ b/src/igc.c
@@ -747,19 +747,41 @@ IGC_DEFINE_LIST (igc_root);
 
 /* Registry entry for an MPS thread mps_thr_t.  */
 
+#include <pthread.h>
+#include <stdatomic.h>
+
+struct emacs_ap
+{
+  mps_ap_t mps_ap;
+  struct igc *gc;
+  pthread_t allocation_thread;
+  atomic_uintptr_t usable_memory;
+  atomic_uintptr_t usable_bytes;
+
+  atomic_uintptr_t waiting_threads;
+  atomic_uintptr_t requested_bytes;
+  atomic_intptr_t requested_type;
+};
+
+typedef struct emacs_ap emacs_ap_t;
+
+#ifndef ATOMIC_POINTER_LOCK_FREE
+#error "this probably won't work"
+#endif
+
 struct igc_thread
 {
   struct igc *gc;
   mps_thr_t thr;
 
   /* Allocation points for the thread.  */
-  mps_ap_t dflt_ap;
-  mps_ap_t leaf_ap;
-  mps_ap_t weak_strong_ap;
-  mps_ap_t weak_weak_ap;
-  mps_ap_t weak_hash_strong_ap;
-  mps_ap_t weak_hash_weak_ap;
-  mps_ap_t immovable_ap;
+  emacs_ap_t dflt_ap;
+  emacs_ap_t leaf_ap;
+  emacs_ap_t weak_strong_ap;
+  emacs_ap_t weak_weak_ap;
+  emacs_ap_t weak_hash_strong_ap;
+  emacs_ap_t weak_hash_weak_ap;
+  emacs_ap_t immovable_ap;
 
   /* Quick access to the roots used for specpdl, bytecode stack and
      control stack.  */
@@ -805,6 +827,8 @@ IGC_DEFINE_LIST (igc_thread);
 
   /* Registered threads.  */
   struct igc_thread_list *threads;
+
+  pthread_cond_t cond;
 };
 
 static bool process_one_message (struct igc *gc);
@@ -2904,8 +2928,84 @@ igc_root_destroy_comp_unit_eph (struct 
Lisp_Native_Comp_Unit *u)
   maybe_destroy_root (&u->data_eph_relocs_root);
 }
 
+static mps_addr_t alloc_impl_raw (size_t size, enum igc_obj_type type, 
mps_ap_t ap);
+static mps_addr_t alloc_impl (size_t size, enum igc_obj_type type, emacs_ap_t 
*ap);
+
+static void *igc_allocation_thread (void *ap_v)
+{
+  emacs_ap_t *ap = ap_v;
+  while (true)
+    {
+      if (ap->requested_bytes)
+       {
+         void *p = alloc_impl_raw (ap->requested_bytes, (enum igc_obj_type) 
ap->requested_type, ap->mps_ap);
+         atomic_store (&ap->usable_memory, (uintptr_t) p);
+         atomic_store (&ap->usable_bytes, ap->requested_bytes);
+         atomic_store (&ap->requested_type, -1);
+         atomic_store (&ap->requested_bytes, 0);
+       }
+    }
+
+  return NULL;
+}
+
+static mps_addr_t alloc_impl (size_t size, enum igc_obj_type type, emacs_ap_t 
*ap)
+{
+  if (size == 0)
+    return 0;
+  while (true)
+    {
+      uintptr_t other_threads = atomic_fetch_add (&ap->waiting_threads, 1);
+      if (other_threads != 0)
+       {
+         /* we know that the other "thread" is actually on top of us,
+          * and we're a signal handler. Wait, should we even be
+          * allocating memory?  We should still eassert that we're the
+          * right thread. */
+         emacs_ap_t saved_state;
+         while (ap->requested_bytes);
+         memcpy (&saved_state, ap, sizeof saved_state);
+         atomic_store (&ap->waiting_threads, 0);
+         mps_addr_t ret = alloc_impl (size, type, ap);
+         atomic_store (&ap->waiting_threads, saved_state.waiting_threads);
+         memcpy (ap, &saved_state, sizeof saved_state);
+         atomic_fetch_add (&ap->waiting_threads, -1);
+         return ret;
+       }
+
+      atomic_store (&ap->requested_type, (uintptr_t) type);
+      atomic_store (&ap->requested_bytes, (uintptr_t) size);
+
+      while (ap->requested_bytes);
+
+      mps_addr_t ret = (mps_addr_t) ap->usable_memory;
+      atomic_fetch_add (&ap->waiting_threads, -1);
+      return ret;
+    }
+}
+
+static mps_res_t emacs_ap_create_k (emacs_ap_t *ap, mps_pool_t pool,
+                                   mps_arg_s *args)
+{
+  atomic_store(&ap->usable_memory, 0);
+  atomic_store(&ap->usable_bytes, 0);
+  atomic_store(&ap->waiting_threads, 0);
+  atomic_store(&ap->requested_bytes, 0);
+
+  pthread_attr_t thread_attr;
+  pthread_attr_init (&thread_attr);
+  pthread_create(&ap->allocation_thread, &thread_attr, igc_allocation_thread, 
ap);
+
+  return mps_ap_create_k (&ap->mps_ap, pool, args);
+}
+
+static void emacs_ap_destroy (emacs_ap_t *ap)
+{
+  return;
+}
+
 static mps_res_t
-create_weak_ap (mps_ap_t *ap, struct igc_thread *t, bool weak)
+create_weak_ap (emacs_ap_t *ap, struct igc_thread *t, bool weak)
 {
   struct igc *gc = t->gc;
   mps_res_t res;
@@ -2914,14 +3014,14 @@ create_weak_ap (mps_ap_t *ap, struct igc_thread *t, 
bool weak)
   {
     MPS_ARGS_ADD (args, MPS_KEY_RANK,
                  weak ? mps_rank_weak () : mps_rank_exact ());
-    res = mps_ap_create_k (ap, pool, args);
+    res = emacs_ap_create_k (ap, pool, args);
   }
   MPS_ARGS_END (args);
   return res;
 }
 
 static mps_res_t
-create_weak_hash_ap (mps_ap_t *ap, struct igc_thread *t, bool weak)
+create_weak_hash_ap (emacs_ap_t *ap, struct igc_thread *t, bool weak)
 {
   struct igc *gc = t->gc;
   mps_res_t res;
@@ -2930,7 +3030,7 @@ create_weak_hash_ap (mps_ap_t *ap, struct igc_thread *t, 
bool weak)
   {
     MPS_ARGS_ADD (args, MPS_KEY_RANK,
                  weak ? mps_rank_weak () : mps_rank_exact ());
-    res = mps_ap_create_k (ap, pool, args);
+    res = emacs_ap_create_k (ap, pool, args);
   }
   MPS_ARGS_END (args);
   return res;
@@ -2940,12 +3040,15 @@ create_weak_hash_ap (mps_ap_t *ap, struct igc_thread 
*t, bool weak)
 create_thread_aps (struct igc_thread *t)
 {
   struct igc *gc = t->gc;
+  pthread_condattr_t condattr;
+  pthread_condattr_init (&condattr);
+  pthread_cond_init (&gc->cond, &condattr);
   mps_res_t res;
-  res = mps_ap_create_k (&t->dflt_ap, gc->dflt_pool, mps_args_none);
+  res = emacs_ap_create_k (&t->dflt_ap, gc->dflt_pool, mps_args_none);
   IGC_CHECK_RES (res);
-  res = mps_ap_create_k (&t->leaf_ap, gc->leaf_pool, mps_args_none);
+  res = emacs_ap_create_k (&t->leaf_ap, gc->leaf_pool, mps_args_none);
   IGC_CHECK_RES (res);
-  res = mps_ap_create_k (&t->immovable_ap, gc->immovable_pool, mps_args_none);
+  res = emacs_ap_create_k (&t->immovable_ap, gc->immovable_pool, 
mps_args_none);
   IGC_CHECK_RES (res);
   res = create_weak_ap (&t->weak_strong_ap, t, false);
   res = create_weak_hash_ap (&t->weak_hash_strong_ap, t, false);
@@ -3007,13 +3110,13 @@ igc_thread_remove (void **pinfo)
   destroy_root (&t->d.stack_root);
   destroy_root (&t->d.specpdl_root);
   destroy_root (&t->d.bc_root);
-  mps_ap_destroy (t->d.dflt_ap);
-  mps_ap_destroy (t->d.leaf_ap);
-  mps_ap_destroy (t->d.weak_strong_ap);
-  mps_ap_destroy (t->d.weak_weak_ap);
-  mps_ap_destroy (t->d.weak_hash_strong_ap);
-  mps_ap_destroy (t->d.weak_hash_weak_ap);
-  mps_ap_destroy (t->d.immovable_ap);
+  emacs_ap_destroy (&t->d.dflt_ap);
+  emacs_ap_destroy (&t->d.leaf_ap);
+  emacs_ap_destroy (&t->d.weak_strong_ap);
+  emacs_ap_destroy (&t->d.weak_weak_ap);
+  emacs_ap_destroy (&t->d.weak_hash_strong_ap);
+  emacs_ap_destroy (&t->d.weak_hash_weak_ap);
+  emacs_ap_destroy (&t->d.immovable_ap);
   mps_thread_dereg (deregister_thread (t));
 }
 
@@ -3677,7 +3780,7 @@ igc_on_idle (void)
   }
 }
 
-static mps_ap_t
+static emacs_ap_t *
 thread_ap (enum igc_obj_type type)
 {
   struct igc_thread_list *t = current_thread->gc_info;
@@ -3698,13 +3801,13 @@ thread_ap (enum igc_obj_type type)
       emacs_abort ();
 
     case IGC_OBJ_MARKER_VECTOR:
-      return t->d.weak_weak_ap;
+      return &t->d.weak_weak_ap;
 
     case IGC_OBJ_WEAK_HASH_TABLE_WEAK_PART:
-      return t->d.weak_hash_weak_ap;
+      return &t->d.weak_hash_weak_ap;
 
     case IGC_OBJ_WEAK_HASH_TABLE_STRONG_PART:
-      return t->d.weak_hash_strong_ap;
+      return &t->d.weak_hash_strong_ap;
 
     case IGC_OBJ_VECTOR:
     case IGC_OBJ_CONS:
@@ -3719,12 +3822,12 @@ thread_ap (enum igc_obj_type type)
     case IGC_OBJ_FACE_CACHE:
     case IGC_OBJ_BLV:
     case IGC_OBJ_HANDLER:
-      return t->d.dflt_ap;
+      return &t->d.dflt_ap;
 
     case IGC_OBJ_STRING_DATA:
     case IGC_OBJ_FLOAT:
     case IGC_OBJ_BYTES:
-      return t->d.leaf_ap;
+      return &t->d.leaf_ap;
     }
   emacs_abort ();
 }
@@ -3796,7 +3899,7 @@ igc_hash (Lisp_Object key)
    object.  */
 
 static mps_addr_t
-alloc_impl (size_t size, enum igc_obj_type type, mps_ap_t ap)
+alloc_impl_raw (size_t size, enum igc_obj_type type, mps_ap_t ap)
 {
   mps_addr_t p UNINIT;
   size = alloc_size (size);
@@ -3845,7 +3948,7 @@ alloc (size_t size, enum igc_obj_type type)
 alloc_immovable (size_t size, enum igc_obj_type type)
 {
   struct igc_thread_list *t = current_thread->gc_info;
-  return alloc_impl (size, type, t->d.immovable_ap);
+  return alloc_impl (size, type, &t->d.immovable_ap);
 }
 
 #ifdef HAVE_MODULES
@@ -4883,17 +4986,17 @@ igc_on_pdump_loaded (void *dump_base, void *hot_start, 
void *hot_end,
 igc_alloc_dump (size_t nbytes)
 {
   igc_assert (global_igc->park_count > 0);
-  mps_ap_t ap = thread_ap (IGC_OBJ_CONS);
+  emacs_ap_t *ap = thread_ap (IGC_OBJ_CONS);
   size_t block_size = igc_header_size () + nbytes;
   mps_addr_t block;
   do
     {
-      mps_res_t res = mps_reserve (&block, ap, block_size);
+      mps_res_t res = mps_reserve (&block, ap->mps_ap, block_size);
       if (res != MPS_RES_OK)
        memory_full (0);
       set_header (block, IGC_OBJ_INVALID, block_size, 0);
     }
-  while (!mps_commit (ap, block, block_size));
+  while (!mps_commit (ap->mps_ap, block, block_size));
   return (char *) block + igc_header_size ();
 }
 

Warnings:

This is the "slow path" only, used for all allocations. Will cause a
great number of busy-looping threads.  Will be very slow.  Creating
additional emacs threads will result in a proportional number of
additional threads, which will be very, very slow, so don't.  Requires
pthread.h and stdatomic.h, and still does things not covered by those
APIs (memcpying over an atomic_uintptr_t, even if we know that its value
won't change, is probably verboten, and definitely should be).  I
*think* this code might work if we allocate from signal handlers, and I
think this code might work on systems that don't have lock-free atomics
(once the #error is removed), but it definitely won't do both at the
same time.

Pip