Refactor atfork handlers

Current implementation (sysdeps/nptl/fork.c) replicates the atfork
handlers list backward to invoke the child handlers after fork/clone
syscall.

The internal atfork handlers is implemented as a single-linked list
so a lock-free algorithm can be used, trading fork mulithread call
performance for some code complexity and dynamic stack allocation
(since the backwards list should not fail).

This patch refactor it to use a dynarary instead of a linked list.
It simplifies the external variables need to be exported and also
the internal atfork handler member definition.

The downside is a serialization of fork call in multithread, since to
operate on the dynarray the internal lock should be used.  However
as noted by Florian, it already acquires external locks for malloc
and libio so it is already hitting some lock contention.  Besides,
posix_spawn should be faster and more scalable to run external programs
in multithread environments.

Checked on x86_64-linux-gnu.

	* nptl/Makefile (routines): Remove unregister-atfork.
	* nptl/register-atfork.c (fork_handler_pool): Remove variable.
	(fork_handler_alloc): Remove function.
	(fork_handlers, fork_handler_init): New variables.
	(__fork_lock): Rename to atfork_lock.
	(__register_atfork, __unregister_atfork, libc_freeres_fn): Rewrite
	to use a dynamic array to add/remove atfork handlers.
	* sysdeps/nptl/fork.c (__libc_fork): Likewise.
	* sysdeps/nptl/fork.h (__fork_lock, __fork_handlers, __linkin_atfork):
	Remove declaration.
	(fork_handler): Remove next, refcntr, and need_signal member.
	(__run_fork_handler_type): New enum.
	(__run_fork_handlers): New prototype.
	* sysdeps/nptl/libc-lockP.h (__libc_atfork): Remove declaration.

3 files changed, 90 insertions, 207 deletions

diff --git a/nptl/Makefile b/nptl/Makefile
index 9340f9f..de37fb4 100644
--- a/nptl/Makefile
+++ b/nptl/Makefile
@@ -30,7 +30,7 @@ install-lib-ldscripts := libpthread.so
 
 routines = alloca_cutoff forward libc-lowlevellock libc-cancellation \
 	   libc-cleanup libc_pthread_init libc_multiple_threads \
-	   register-atfork unregister-atfork pthread_self
+	   register-atfork pthread_self
 shared-only-routines = forward
 
 # We need to provide certain routines for compatibility with existing
diff --git a/nptl/register-atfork.c b/nptl/register-atfork.c
index f309cec..5ff1c1b 100644
--- a/nptl/register-atfork.c
+++ b/nptl/register-atfork.c
@@ -22,123 +22,127 @@
 #include <fork.h>
 #include <atomic.h>
 
+#define DYNARRAY_ELEMENT           struct fork_handler
+#define DYNARRAY_STRUCT            fork_handler_list
+#define DYNARRAY_PREFIX            fork_handler_list_
+#define DYNARRAY_INITIAL_SIZE      48
+#include <malloc/dynarray-skeleton.c>
 
-struct fork_handler *__fork_handlers;
-
-/* Lock to protect allocation and deallocation of fork handlers.  */
-int __fork_lock = LLL_LOCK_INITIALIZER;
-
-
-/* Number of pre-allocated handler entries.  */
-#define NHANDLER 48
-
-/* Memory pool for fork handler structures.  */
-static struct fork_handler_pool
-{
-  struct fork_handler_pool *next;
-  struct fork_handler mem[NHANDLER];
-} fork_handler_pool;
-
-
-static struct fork_handler *
-fork_handler_alloc (void)
-{
-  struct fork_handler_pool *runp = &fork_handler_pool;
-  struct fork_handler *result = NULL;
-  unsigned int i;
-
-  do
-    {
-      /* Search for an empty entry.  */
-      for (i = 0; i < NHANDLER; ++i)
-	if (runp->mem[i].refcntr == 0)
-	  goto found;
-    }
-  while ((runp = runp->next) != NULL);
-
-  /* We have to allocate a new entry.  */
-  runp = (struct fork_handler_pool *) calloc (1, sizeof (*runp));
-  if (runp != NULL)
-    {
-      /* Enqueue the new memory pool into the list.  */
-      runp->next = fork_handler_pool.next;
-      fork_handler_pool.next = runp;
-
-      /* We use the last entry on the page.  This means when we start
-	 searching from the front the next time we will find the first
-	 entry unused.  */
-      i = NHANDLER - 1;
-
-    found:
-      result = &runp->mem[i];
-      result->refcntr = 1;
-      result->need_signal = 0;
-    }
-
-  return result;
-}
+static struct fork_handler_list fork_handlers;
+static bool fork_handler_init = false;
 
+static int atfork_lock = LLL_LOCK_INITIALIZER;
 
 int
 __register_atfork (void (*prepare) (void), void (*parent) (void),
 		   void (*child) (void), void *dso_handle)
 {
-  /* Get the lock to not conflict with other allocations.  */
-  lll_lock (__fork_lock, LLL_PRIVATE);
+  lll_lock (atfork_lock, LLL_PRIVATE);
 
-  struct fork_handler *newp = fork_handler_alloc ();
+  if (!fork_handler_init)
+    {
+      fork_handler_list_init (&fork_handlers);
+      fork_handler_init = true;
+    }
 
+  struct fork_handler *newp = fork_handler_list_emplace (&fork_handlers);
   if (newp != NULL)
     {
-      /* Initialize the new record.  */
       newp->prepare_handler = prepare;
       newp->parent_handler = parent;
       newp->child_handler = child;
       newp->dso_handle = dso_handle;
-
-      __linkin_atfork (newp);
     }
 
   /* Release the lock.  */
-  lll_unlock (__fork_lock, LLL_PRIVATE);
+  lll_unlock (atfork_lock, LLL_PRIVATE);
 
   return newp == NULL ? ENOMEM : 0;
 }
 libc_hidden_def (__register_atfork)
 
+static struct fork_handler *
+fork_handler_list_find (struct fork_handler_list *fork_handlers,
+			void *dso_handle)
+{
+  for (size_t i = 0; i < fork_handler_list_size (fork_handlers); i++)
+    {
+      struct fork_handler *elem = fork_handler_list_at (fork_handlers, i);
+      if (elem->dso_handle == dso_handle)
+	return elem;
+    }
+  return NULL;
+}
 
 void
-attribute_hidden
-__linkin_atfork (struct fork_handler *newp)
+__unregister_atfork (void *dso_handle)
 {
-  do
-    newp->next = __fork_handlers;
-  while (catomic_compare_and_exchange_bool_acq (&__fork_handlers,
-						newp, newp->next) != 0);
-}
+  lll_lock (atfork_lock, LLL_PRIVATE);
+
+  struct fork_handler *first = fork_handler_list_find (&fork_handlers,
+						       dso_handle);
+  /* Removing is done by shifting the elements in the way the elements
+     that are not to be removed appear in the beginning in dynarray.
+     This avoid the quadradic run-time if a naive strategy to remove and
+     shift one element at time.  */
+  if (first != NULL)
+    {
+      struct fork_handler *new_end = first;
+      first++;
+      for (; first != fork_handler_list_end (&fork_handlers); ++first)
+	{
+	  if (first->dso_handle != dso_handle)
+	    {
+	      *new_end = *first;
+	      ++new_end;
+	    }
+	}
+
+      ptrdiff_t removed = first - new_end;
+      for (size_t i = 0; i < removed; i++)
+	fork_handler_list_remove_last (&fork_handlers);
+    }
 
+  lll_unlock (atfork_lock, LLL_PRIVATE);
+}
 
-libc_freeres_fn (free_mem)
+void
+__run_fork_handlers (enum __run_fork_handler_type who)
 {
-  /* Get the lock to not conflict with running forks.  */
-  lll_lock (__fork_lock, LLL_PRIVATE);
+  struct fork_handler *runp;
 
-  /* No more fork handlers.  */
-  __fork_handlers = NULL;
+  if (who == atfork_run_prepare)
+    {
+      lll_lock (atfork_lock, LLL_PRIVATE);
+      size_t sl = fork_handler_list_size (&fork_handlers);
+      for (size_t i = sl; i > 0; i--)
+	{
+	  runp = fork_handler_list_at (&fork_handlers, i - 1);
+	  if (runp->prepare_handler != NULL)
+	    runp->prepare_handler ();
+	}
+    }
+  else
+    {
+      size_t sl = fork_handler_list_size (&fork_handlers);
+      for (size_t i = 0; i < sl; i++)
+	{
+	  runp = fork_handler_list_at (&fork_handlers, i);
+	  if (who == atfork_run_child && runp->child_handler)
+	    runp->child_handler ();
+	  else if (who == atfork_run_parent && runp->parent_handler)
+	    runp->parent_handler ();
+	}
+      lll_unlock (atfork_lock, LLL_PRIVATE);
+    }
+}
 
-  /* Free eventually allocated memory blocks for the object pool.  */
-  struct fork_handler_pool *runp = fork_handler_pool.next;
 
-  memset (&fork_handler_pool, '\0', sizeof (fork_handler_pool));
+libc_freeres_fn (free_mem)
+{
+  lll_lock (atfork_lock, LLL_PRIVATE);
 
-  /* Release the lock.  */
-  lll_unlock (__fork_lock, LLL_PRIVATE);
+  fork_handler_list_free (&fork_handlers);
 
-  /* We can free the memory after releasing the lock.  */
-  while (runp != NULL)
-    {
-      struct fork_handler_pool *oldp = runp;
-      runp = runp->next;
-      free (oldp);
-    }
+  lll_unlock (atfork_lock, LLL_PRIVATE);
 }
diff --git a/nptl/unregister-atfork.c b/nptl/unregister-atfork.c
deleted file mode 100644
index 20411ed..0000000
--- a/nptl/unregister-atfork.c
+++ /dev/null
@@ -1,121 +0,0 @@
-/* Copyright (C) 2002-2018 Free Software Foundation, Inc.
-   This file is part of the GNU C Library.
-   Contributed by Ulrich Drepper <drepper@redhat.com>, 2002.
-
-   The GNU C Library is free software; you can redistribute it and/or
-   modify it under the terms of the GNU Lesser General Public
-   License as published by the Free Software Foundation; either
-   version 2.1 of the License, or (at your option) any later version.
-
-   The GNU C Library 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
-   Lesser General Public License for more details.
-
-   You should have received a copy of the GNU Lesser General Public
-   License along with the GNU C Library; if not, see
-   <http://www.gnu.org/licenses/>.  */
-
-#include <errno.h>
-#include <stdlib.h>
-#include <fork.h>
-#include <atomic.h>
-#include <futex-internal.h>
-
-
-void
-__unregister_atfork (void *dso_handle)
-{
-  /* Check whether there is any entry in the list which we have to
-     remove.  It is likely that this is not the case so don't bother
-     getting the lock.
-
-     We do not worry about other threads adding entries for this DSO
-     right this moment.  If this happens this is a race and we can do
-     whatever we please.  The program will crash anyway seen.  */
-  struct fork_handler *runp = __fork_handlers;
-  struct fork_handler *lastp = NULL;
-
-  while (runp != NULL)
-    if (runp->dso_handle == dso_handle)
-      break;
-    else
-      {
-	lastp = runp;
-	runp = runp->next;
-      }
-
-  if (runp == NULL)
-    /* Nothing to do.  */
-    return;
-
-  /* Get the lock to not conflict with additions or deletions.  Note
-     that there couldn't have been another thread deleting something.
-     The __unregister_atfork function is only called from the
-     dlclose() code which itself serializes the operations.  */
-  lll_lock (__fork_lock, LLL_PRIVATE);
-
-  /* We have to create a new list with all the entries we don't remove.  */
-  struct deleted_handler
-  {
-    struct fork_handler *handler;
-    struct deleted_handler *next;
-  } *deleted = NULL;
-
-  /* Remove the entries for the DSO which is unloaded from the list.
-     It's a single linked list so readers are.  */
-  do
-    {
-    again:
-      if (runp->dso_handle == dso_handle)
-	{
-	  if (lastp == NULL)
-	    {
-	      /* We have to use an atomic operation here because
-		 __linkin_atfork also uses one.  */
-	      if (catomic_compare_and_exchange_bool_acq (&__fork_handlers,
-							 runp->next, runp)
-		  != 0)
-		{
-		  runp = __fork_handlers;
-		  goto again;
-		}
-	    }
-	  else
-	    lastp->next = runp->next;
-
-	  /* We cannot overwrite the ->next element now.  Put the deleted
-	     entries in a separate list.  */
-	  struct deleted_handler *newp = alloca (sizeof (*newp));
-	  newp->handler = runp;
-	  newp->next = deleted;
-	  deleted = newp;
-	}
-      else
-	lastp = runp;
-
-      runp = runp->next;
-    }
-  while (runp != NULL);
-
-  /* Release the lock.  */
-  lll_unlock (__fork_lock, LLL_PRIVATE);
-
-  /* Walk the list of all entries which have to be deleted.  */
-  while (deleted != NULL)
-    {
-      /* We need to be informed by possible current users.  */
-      deleted->handler->need_signal = 1;
-      /* Make sure this gets written out first.  */
-      atomic_write_barrier ();
-
-      /* Decrement the reference counter.  If it does not reach zero
-	 wait for the last user.  */
-      atomic_decrement (&deleted->handler->refcntr);
-      unsigned int val;
-      while ((val = deleted->handler->refcntr) != 0)
-	futex_wait_simple (&deleted->handler->refcntr, val, FUTEX_PRIVATE);
-
-      deleted = deleted->next;
-    }
-}