Implement allocate_once (was: Re: [PATCH] Implement libc_once_retry for atomic initialization with allocation)

On 01/05/2018 12:08 PM, Florian Weimer wrote:
> On 01/04/2018 07:33 PM, Torvald Riegel wrote:
> 
>> Maybe sth like libc_allocate_and_init_once, or just libc_init_once?  One
>> can do without allocation if setting DEALLOCATE to an empty function,
>> but the parameters really suggest that this is about allocation.
> 
> If DEALLOCATE does nothing, you can just use a simple atomic store. 8-) 
> (Which is why I used NULL to denote free, not a nop.)
> 
>>> /* Perform an acquire MO load on *PLACE.  If *PLACE is not NULL,
>>>      return *PLACE.  Otherwise, call ALLOCATE (CLOSURE), yielding
>>>      RESULT.  If RESULT equals NULL, return NULL.  Otherwise, atomically
>>>      replace the NULL value in *PLACE with the RESULT value.  If it
>>
>> You don't replace it atomically though, you really do run a CAS that
>> ensures that you replace iff *PLACE is still NULL.
> 
> Please have a look at the updated documentation in the attached patch.

I botched the PLT avoidance, so here is the next version.

Thanks,
Florian

On 01/09/2018 12:07 PM, Florian Weimer wrote:
> On 01/05/2018 12:08 PM, Florian Weimer wrote:
>> On 01/04/2018 07:33 PM, Torvald Riegel wrote:
>>
>>> Maybe sth like libc_allocate_and_init_once, or just libc_init_once?  One
>>> can do without allocation if setting DEALLOCATE to an empty function,
>>> but the parameters really suggest that this is about allocation.
>>
>> If DEALLOCATE does nothing, you can just use a simple atomic store. 8-) (Which is why I used NULL to denote free, not a nop.)
>>
>>>> /* Perform an acquire MO load on *PLACE.  If *PLACE is not NULL,
>>>>      return *PLACE.  Otherwise, call ALLOCATE (CLOSURE), yielding
>>>>      RESULT.  If RESULT equals NULL, return NULL.  Otherwise, atomically
>>>>      replace the NULL value in *PLACE with the RESULT value.  If it
>>>
>>> You don't replace it atomically though, you really do run a CAS that
>>> ensures that you replace iff *PLACE is still NULL.
>>
>> Please have a look at the updated documentation in the attached patch.
> 
> I botched the PLT avoidance, so here is the next version.

See my questions inline below. I think this is pretty close to ready.

High level:

I like the use pattern of allocate_once, and you've written some good
documentation.

Design:

I'd like to see some clarification of the failure semantics. I added
some comments bellow.

We don't verify free() is called in the test case without the explicit
deallocate. Should we use MALLOC_TRACE to verify it?

Implementation:

Minor comment typo.

> Subject: [PATCH] Implement allocate_once for atomic initialization with allocation
> To: libc-alpha@sourceware.org
> 
> 2018-01-04  Florian Weimer  <fweimer@redhat.com>
> 
> 	Implement allocate_once.
> 	* include/allocate_once.h: New file.
> 	* misc/allocate_once.c: Likewise.
> 	* misc/tst-allocate_once.c: Likewise.
> 	* misc/Makefile (routines): Add allocate_once.
> 	(tests-internal): Add tst-allocate_once.
> 	* misc/Versions (GLIBC_PRIVATE): Add __libc_allocate_once_slow.
> 
> diff --git a/include/allocate_once.h b/include/allocate_once.h
> new file mode 100644
> index 0000000000..a96dfe8432
> --- /dev/null
> +++ b/include/allocate_once.h
> @@ -0,0 +1,92 @@
> +/* Allocate and initialize and object once, in a thread-safe fashion.

OK.

> +   Copyright (C) 2018 Free Software Foundation, Inc.
> +   This file is part of the GNU C Library.
> +
> +   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/>.  */
> +
> +#ifndef _ALLOCATE_ONCE_H
> +#define _ALLOCATE_ONCE_H
> +
> +#include <atomic.h>
> +
> +/* Slow path for allocate_once; see below.  */
> +void *__libc_allocate_once_slow (void **__place,
> +                                 void *(*__allocate) (void *__closure),
> +                                 void (*__deallocate) (void *__closure,
> +                                                       void *__ptr),
> +                                 void *__closure);
> +
> +/* Return an a pointer to an allocated and initialized data structure.
> +   If this function returns a non-NULL value, the caller can assume
> +   that pointed-to data has been initialized according to the ALLOCATE
> +   function.
> +
> +   It is expected that callers define an inline helper function which
> +   adds type safety, like this.
> +
> +   struct foo { ... };
> +   struct foo *global_foo;
> +   static void *allocate_foo (void *closure);
> +   static void *deallocate_foo (void *closure, void *ptr);
> +
> +   static inline struct foo *
> +   get_foo (void)
> +   {
> +     return allocate_once (&global_foo, allocate_foo, free_foo, NULL);
> +   }
> +
> +   (Note that the global_foo variable is initialized to zero.)
> +   Usage of this helper function looks like this:
> +
> +   struct foo *local_foo = get_foo ();
> +   if (local_foo == NULL)
> +      report_allocation_failure ();

OK.

> +
> +   allocate_once first performs an acquire MO load on *PLACE.  If the
> +   result is not null, it is returned.  Otherwise, ALLOCATE (CLOSURE)
> +   is called, yielding a value RESULT.  If RESULT equals NULL,
> +   allocate_once returns NULL.  

There are some non-obvious consequences to failure which I think we should
call out.

Suggest:

The allocation failure in one thread may be completed in another, therefore
care should be taken in the failed thread to avoid data races with in 
progress initialization from other threads. The implementation will not
change the value of *PLACE after allocation failure.

                                   Otherwise, the function uses CAS to
> +   update the NULL value in *PLACE with the RESULT value.  If it turns
> +   out that *PLACE was updated concurrently, allocate_once calls
> +   DEALLOCATE (CLOSURE, RESULT) to undo the effect of ALLOCATE, and
> +   returns the new value of *PLACE (after an acquire MO load).  If
> +   DEALLOCATE is NULL, free (RESULT) is called instead.
> +
> +   Compared to __libc_once, allocate_once has the advantage that it
> +   does not need separate space for a control variable, and that it is
> +   safe with regards to cancellation and other forms of exception
> +   handling if the supplied callback functions are safe in that
> +   regard.  allocate_once passes a closure parameter to the allocation
> +   function, too.  */
> +static inline void *
> +allocate_once (void **__place, void *(*__allocate) (void *__closure),
> +               void (*__deallocate) (void *__closure, void *__ptr),
> +               void *__closure)
> +{
> +  /* Synchronizes with the release MO CAS in
> +     __allocate_once_slow.  */
> +  void *__result = atomic_load_acquire (__place);

OK. This synchronizes with the CAS in the slow path.

> +  if (__result != NULL)
> +    return __result;
> +  else
> +    return __libc_allocate_once_slow (__place, __allocate, __deallocate,
> +                                      __closure);
> +}
> +
> +#ifndef _ISOMAC
> +libc_hidden_proto (__libc_allocate_once_slow)
> +#endif
> +
> +#endif /* _ALLOCATE_ONCE_H */
> diff --git a/misc/Makefile b/misc/Makefile
> index a5076b3672..1fccb729a5 100644
> --- a/misc/Makefile
> +++ b/misc/Makefile
> @@ -70,7 +70,8 @@ routines := brk sbrk sstk ioctl \
>  	    getloadavg getclktck \
>  	    fgetxattr flistxattr fremovexattr fsetxattr getxattr \
>  	    listxattr lgetxattr llistxattr lremovexattr lsetxattr \
> -	    removexattr setxattr getauxval ifunc-impl-list makedev
> +	    removexattr setxattr getauxval ifunc-impl-list makedev \
> +	    allocate_once

OK.

>  
>  generated += tst-error1.mtrace tst-error1-mem.out
>  
> @@ -84,7 +85,7 @@ tests := tst-dirname tst-tsearch tst-fdset tst-efgcvt tst-mntent tst-hsearch \
>  	 tst-preadvwritev tst-preadvwritev64 tst-makedev tst-empty \
>  	 tst-preadvwritev2 tst-preadvwritev64v2
>  
> -tests-internal := tst-atomic tst-atomic-long
> +tests-internal := tst-atomic tst-atomic-long tst-allocate_once

OK.

>  tests-static := tst-empty
>  
>  ifeq ($(run-built-tests),yes)
> diff --git a/misc/Versions b/misc/Versions
> index bfbda505e4..900e4ffb79 100644
> --- a/misc/Versions
> +++ b/misc/Versions
> @@ -165,5 +165,6 @@ libc {
>      __tdelete; __tfind; __tsearch; __twalk;
>      __mmap; __munmap; __mprotect;
>      __sched_get_priority_min; __sched_get_priority_max;
> +    __libc_allocate_once_slow;

OK.

>    }
>  }
> diff --git a/misc/allocate_once.c b/misc/allocate_once.c
> new file mode 100644
> index 0000000000..2108014604
> --- /dev/null
> +++ b/misc/allocate_once.c
> @@ -0,0 +1,59 @@
> +/* Concurrent allocation and initialization of a pointer.
> +   Copyright (C) 2018 Free Software Foundation, Inc.
> +   This file is part of the GNU C Library.
> +
> +   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 <allocate_once.h>
> +#include <stdlib.h>
> +#include <stdbool.h>
> +
> +void *
> +__libc_allocate_once_slow (void **place, void *(*allocate) (void *closure),
> +                           void (*deallocate) (void *closure, void *ptr),
> +                           void *closure)
> +{
> +  void *result = allocate (closure);
> +  if (result == NULL)
> +    return NULL;

OK.

> +
> +  /* This loop implements a strong CAS on *place, with acquire-release
> +     MO semantics, from a weak CAS with relaxed-release MO.  */
> +  while (true)
> +    {
> +      /* Synchronizes with the acquire MO load in allocate_once.  */
> +      void *expected = NULL;
> +      if (atomic_compare_exchange_weak_release (place, &expected, result))
> +        return result;
> +
> +      /* The failed CAS has relaxed MO semantics, so perform another
> +         acquire MO load.  */
> +      void *other_result = atomic_load_acquire (place);
> +      if (other_result == NULL)
> +        /* Spurious failure.  Try again.  */
> +        continue;
> +
> +      /* We lost the race.  Free what we allocated and return the
> +         other result.  */
> +      if (deallocate == NULL)
> +        free (result);
> +      else
> +        deallocate (closure, result);
> +      return other_result;
> +    }
> +
> +  return result;
> +}
> +libc_hidden_def (__libc_allocate_once_slow)
> diff --git a/misc/tst-allocate_once.c b/misc/tst-allocate_once.c
> new file mode 100644
> index 0000000000..2d18aa04ab
> --- /dev/null
> +++ b/misc/tst-allocate_once.c
> @@ -0,0 +1,175 @@
> +/* Test the allocate_once function.
> +   Copyright (C) 2018 Free Software Foundation, Inc.
> +   This file is part of the GNU C Library.
> +
> +   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 <allocate_once.h>
> +#include <string.h>
> +#include <support/check.h>
> +#include <support/support.h>
> +
> +/* Allocate a new string.  */
> +static void *
> +allocate_string (void *closure)
> +{
> +  return xstrdup (closure);
> +}

OK.

> +
> +/* Allocation and deallocation functions which are not expected to be
> +   called.  */
> +
> +static void *
> +allocate_not_called (void *closure)
> +{
> +  FAIL_EXIT1 ("allocation function called unexpectedly (%p)", closure);
> +}

OK.

> +
> +static void
> +deallocate_not_called (void *closure, void *ptr)
> +{
> +  FAIL_EXIT1 ("deallocate function called unexpectedly (%p, %p)",
> +              closure, ptr);
> +}

OK.

> +
> +/* Counter for various function calls.  */
> +static int function_called;
> +
> +/* An allocation function which returns NULL and records that it has
> +   been called.  */
> +static void *
> +allocate_return_null (void *closure)
> +{
> +  /* The function should only be called once.  */
> +  TEST_COMPARE (function_called, 0);
> +  ++function_called;
> +  return NULL;
> +}

OK.

> +
> +
> +/* The following is used to check the retry logic, by causing a fake
> +   race condition.  */
> +static void *fake_race_place;
> +static char fake_race_region[3]; /* To obtain unique addresses.  */
> +
> +static void *
> +fake_race_allocate (void *closure)
> +{
> +  TEST_VERIFY (closure == &fake_race_region[0]);
> +  TEST_COMPARE (function_called, 0);
> +  ++function_called;
> +  /* Fake allocation by another thread.  */
> +  fake_race_place = &fake_race_region[1];
> +  return &fake_race_region[2];
> +}

OK.

> +
> +static void
> +fake_race_deallocate (void *closure, void *ptr)
> +{
> +  /* Check that the pointer returned from fake_race_allocate is
> +     deallocated (and not the one stored in fake_race_place).  */
> +  TEST_VERIFY (ptr == &fake_race_region[2]);
> +
> +  TEST_VERIFY (fake_race_place == &fake_race_region[1]);
> +  TEST_VERIFY (closure == &fake_race_region[0]);
> +  TEST_COMPARE (function_called, 1);
> +  ++function_called;
> +}

OK.

> +
> +/* Similar to fake_race_allocate, but expects to be paired with free
> +   as the deallocation function.  */
> +static void *
> +fake_race_allocate_for_free (void *closure)
> +{
> +  TEST_VERIFY (closure == &fake_race_region[0]);
> +  TEST_COMPARE (function_called, 0);
> +  ++function_called;
> +  /* Fake allocation by another thread.  */
> +  fake_race_place = &fake_race_region[1];
> +  return xstrdup ("to be freed");
> +}

OK.

> +
> +static int
> +do_test (void)
> +{
> +  /* Simple allocation.  */
> +  void *place1 = NULL;
> +  char *string1 = allocate_once (&place1, allocate_string,
> +                                   deallocate_not_called,
> +                                   (char *) "test string 1");
> +  TEST_VERIFY_EXIT (string1 != NULL);
> +  TEST_VERIFY (strcmp ("test string 1", string1) == 0);

OK.

> +  /* Second call returns the first pointer, without calling any
> +     callbacks.  */
> +  TEST_VERIFY (string1
> +               == allocate_once (&place1, allocate_not_called,
> +                                 deallocate_not_called,
> +                                 (char *) "test string 1a"));

OK. Changed closure, but result is still string1.

> +
> +  /* Difference place should result in another call.  */

s/Difference/Different/g

> +  void *place2 = NULL;
> +  char *string2 = allocate_once (&place2, allocate_string,
> +                                 deallocate_not_called,
> +                                 (char *) "test string 2");
> +  TEST_VERIFY_EXIT (string2 != NULL);
> +  TEST_VERIFY (strcmp ("test string 2", string2) == 0);
> +  TEST_VERIFY (string1 != string2);

OK.

> +
> +  /* Check error reporting (NULL return value from the allocation
> +     function).  */
> +  void *place3 = NULL;
> +  char *string3 = allocate_once (&place3, allocate_return_null,
> +                                 deallocate_not_called, NULL);
> +  TEST_VERIFY (string3 == NULL);
> +  TEST_COMPARE (function_called, 1);

OK.

> +
> +  /* Check that the deallocation function is called if the race is
> +     lost.  */
> +  function_called = 0;
> +  TEST_VERIFY (allocate_once (&fake_race_place,
> +                              fake_race_allocate,
> +                              fake_race_deallocate,
> +                              &fake_race_region[0])
> +               == &fake_race_region[1]);
> +  TEST_COMPARE (function_called, 2);

OK.

> +  function_called = 3;
> +  TEST_VERIFY (allocate_once (&fake_race_place,
> +                              fake_race_allocate,
> +                              fake_race_deallocate,
> +                              &fake_race_region[0])
> +               == &fake_race_region[1]);
> +  TEST_COMPARE (function_called, 3);

OK. No calls to anything.

> +
> +  /* Similar, but this time rely on that free is called.  */
> +  function_called = 0;
> +  fake_race_place = NULL;
> +  TEST_VERIFY (allocate_once (&fake_race_place,
> +                                fake_race_allocate_for_free,
> +                                NULL,
> +                                &fake_race_region[0])
> +               == &fake_race_region[1]);
> +  TEST_COMPARE (function_called, 1);

How do you know free was called without using MALLOC_TRACE to verify it?

> +  function_called = 3;
> +  TEST_VERIFY (allocate_once (&fake_race_place,
> +                              fake_race_allocate_for_free,
> +                              NULL,
> +                              &fake_race_region[0])
> +               == &fake_race_region[1]);
> +  TEST_COMPARE (function_called, 3);
> +

OK.

> +  return 0;
> +}
> +
> +#include <support/test-driver.c>

On 01/11/2018 12:24 AM, Carlos O'Donell wrote:

> We don't verify free() is called in the test case without the explicit
> deallocate. Should we use MALLOC_TRACE to verify it?

I added mtrace, fixed the typo, and updated the documentation comment.

I will commit this once 2.28 opens for development.

Thanks,
Florian
Subject: [PATCH] Implement allocate_once for atomic initialization with allocation
To: libc-alpha@sourceware.org

2018-01-12  Florian Weimer  <fweimer@redhat.com>

	Implement allocate_once.
	* include/allocate_once.h: New file.
	* misc/allocate_once.c: Likewise.
	* misc/tst-allocate_once.c: Likewise.
	* misc/Makefile (routines): Add allocate_once.
	(tests-internal): Add tst-allocate_once.
	(generated): Add tst-allocate_once.mtrace,
	tst-allocate_once-mem.out.
	(tests-special): Add tst-allocate_once-mem.out.
	(tst-allocate_once-ENV): Set MALLOC_TRACE.
	(tst-allocate_once-mem.out): Call mtrace.
	* misc/Versions (GLIBC_PRIVATE): Add __libc_allocate_once_slow.

diff --git a/include/allocate_once.h b/include/allocate_once.h
new file mode 100644
index 0000000000..750e116954
--- /dev/null
+++ b/include/allocate_once.h
@@ -0,0 +1,95 @@
+/* Allocate and initialize and object once, in a thread-safe fashion.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   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/>.  */
+
+#ifndef _ALLOCATE_ONCE_H
+#define _ALLOCATE_ONCE_H
+
+#include <atomic.h>
+
+/* Slow path for allocate_once; see below.  */
+void *__libc_allocate_once_slow (void **__place,
+                                 void *(*__allocate) (void *__closure),
+                                 void (*__deallocate) (void *__closure,
+                                                       void *__ptr),
+                                 void *__closure);
+
+/* Return an a pointer to an allocated and initialized data structure.
+   If this function returns a non-NULL value, the caller can assume
+   that pointed-to data has been initialized according to the ALLOCATE
+   function.
+
+   It is expected that callers define an inline helper function which
+   adds type safety, like this.
+
+   struct foo { ... };
+   struct foo *global_foo;
+   static void *allocate_foo (void *closure);
+   static void *deallocate_foo (void *closure, void *ptr);
+
+   static inline struct foo *
+   get_foo (void)
+   {
+     return allocate_once (&global_foo, allocate_foo, free_foo, NULL);
+   }
+
+   (Note that the global_foo variable is initialized to zero.)
+   Usage of this helper function looks like this:
+
+   struct foo *local_foo = get_foo ();
+   if (local_foo == NULL)
+      report_allocation_failure ();
+
+   allocate_once first performs an acquire MO load on *PLACE.  If the
+   result is not null, it is returned.  Otherwise, ALLOCATE (CLOSURE)
+   is called, yielding a value RESULT.  If RESULT equals NULL,
+   allocate_once returns NULL, and does not modify *PLACE (but another
+   thread may concurrently perform an allocation which succeeds,
+   updating *PLACE).  If RESULT does not equal NULL, the function uses
+   a CAS with acquire-release MO to update the NULL value in *PLACE
+   with the RESULT value.  If it turns out that *PLACE was updated
+   concurrently, allocate_once calls DEALLOCATE (CLOSURE, RESULT) to
+   undo the effect of ALLOCATE, and returns the new value of *PLACE
+   (after an acquire MO load).  If DEALLOCATE is NULL, free (RESULT)
+   is called instead.
+
+   Compared to __libc_once, allocate_once has the advantage that it
+   does not need separate space for a control variable, and that it is
+   safe with regards to cancellation and other forms of exception
+   handling if the supplied callback functions are safe in that
+   regard.  allocate_once passes a closure parameter to the allocation
+   function, too.  */
+static inline void *
+allocate_once (void **__place, void *(*__allocate) (void *__closure),
+               void (*__deallocate) (void *__closure, void *__ptr),
+               void *__closure)
+{
+  /* Synchronizes with the release MO CAS in
+     __allocate_once_slow.  */
+  void *__result = atomic_load_acquire (__place);
+  if (__result != NULL)
+    return __result;
+  else
+    return __libc_allocate_once_slow (__place, __allocate, __deallocate,
+                                      __closure);
+}
+
+#ifndef _ISOMAC
+libc_hidden_proto (__libc_allocate_once_slow)
+#endif
+
+#endif /* _ALLOCATE_ONCE_H */
diff --git a/misc/Makefile b/misc/Makefile
index a5076b3672..96afd6d890 100644
--- a/misc/Makefile
+++ b/misc/Makefile
@@ -70,9 +70,11 @@ routines := brk sbrk sstk ioctl \
 	    getloadavg getclktck \
 	    fgetxattr flistxattr fremovexattr fsetxattr getxattr \
 	    listxattr lgetxattr llistxattr lremovexattr lsetxattr \
-	    removexattr setxattr getauxval ifunc-impl-list makedev
+	    removexattr setxattr getauxval ifunc-impl-list makedev \
+	    allocate_once
 
-generated += tst-error1.mtrace tst-error1-mem.out
+generated += tst-error1.mtrace tst-error1-mem.out \
+  tst-allocate_once.mtrace tst-allocate_once-mem.out
 
 aux := init-misc
 install-lib := libg.a
@@ -84,11 +86,12 @@ tests := tst-dirname tst-tsearch tst-fdset tst-efgcvt tst-mntent tst-hsearch \
 	 tst-preadvwritev tst-preadvwritev64 tst-makedev tst-empty \
 	 tst-preadvwritev2 tst-preadvwritev64v2
 
-tests-internal := tst-atomic tst-atomic-long
+tests-internal := tst-atomic tst-atomic-long tst-allocate_once
 tests-static := tst-empty
 
 ifeq ($(run-built-tests),yes)
-tests-special += $(objpfx)tst-error1-mem.out
+tests-special += $(objpfx)tst-error1-mem.out \
+  $(objpfx)tst-allocate_once-mem.out
 endif
 
 CFLAGS-select.c += -fexceptions -fasynchronous-unwind-tables
@@ -137,3 +140,8 @@ tst-error1-ARGS = $(objpfx)tst-error1.out
 $(objpfx)tst-error1-mem.out: $(objpfx)tst-error1.out
 	$(common-objpfx)malloc/mtrace $(objpfx)tst-error1.mtrace > $@; \
 	$(evaluate-test)
+
+tst-allocate_once-ENV = MALLOC_TRACE=$(objpfx)tst-allocate_once.mtrace
+$(objpfx)tst-allocate_once-mem.out: $(objpfx)tst-allocate_once.out
+	$(common-objpfx)malloc/mtrace $(objpfx)tst-allocate_once.mtrace > $@; \
+	$(evaluate-test)
diff --git a/misc/Versions b/misc/Versions
index bfbda505e4..900e4ffb79 100644
--- a/misc/Versions
+++ b/misc/Versions
@@ -165,5 +165,6 @@ libc {
     __tdelete; __tfind; __tsearch; __twalk;
     __mmap; __munmap; __mprotect;
     __sched_get_priority_min; __sched_get_priority_max;
+    __libc_allocate_once_slow;
   }
 }
diff --git a/misc/allocate_once.c b/misc/allocate_once.c
new file mode 100644
index 0000000000..2108014604
--- /dev/null
+++ b/misc/allocate_once.c
@@ -0,0 +1,59 @@
+/* Concurrent allocation and initialization of a pointer.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   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 <allocate_once.h>
+#include <stdlib.h>
+#include <stdbool.h>
+
+void *
+__libc_allocate_once_slow (void **place, void *(*allocate) (void *closure),
+                           void (*deallocate) (void *closure, void *ptr),
+                           void *closure)
+{
+  void *result = allocate (closure);
+  if (result == NULL)
+    return NULL;
+
+  /* This loop implements a strong CAS on *place, with acquire-release
+     MO semantics, from a weak CAS with relaxed-release MO.  */
+  while (true)
+    {
+      /* Synchronizes with the acquire MO load in allocate_once.  */
+      void *expected = NULL;
+      if (atomic_compare_exchange_weak_release (place, &expected, result))
+        return result;
+
+      /* The failed CAS has relaxed MO semantics, so perform another
+         acquire MO load.  */
+      void *other_result = atomic_load_acquire (place);
+      if (other_result == NULL)
+        /* Spurious failure.  Try again.  */
+        continue;
+
+      /* We lost the race.  Free what we allocated and return the
+         other result.  */
+      if (deallocate == NULL)
+        free (result);
+      else
+        deallocate (closure, result);
+      return other_result;
+    }
+
+  return result;
+}
+libc_hidden_def (__libc_allocate_once_slow)
diff --git a/misc/tst-allocate_once.c b/misc/tst-allocate_once.c
new file mode 100644
index 0000000000..89277b33b7
--- /dev/null
+++ b/misc/tst-allocate_once.c
@@ -0,0 +1,181 @@
+/* Test the allocate_once function.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   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 <allocate_once.h>
+#include <mcheck.h>
+#include <string.h>
+#include <support/check.h>
+#include <support/support.h>
+
+/* Allocate a new string.  */
+static void *
+allocate_string (void *closure)
+{
+  return xstrdup (closure);
+}
+
+/* Allocation and deallocation functions which are not expected to be
+   called.  */
+
+static void *
+allocate_not_called (void *closure)
+{
+  FAIL_EXIT1 ("allocation function called unexpectedly (%p)", closure);
+}
+
+static void
+deallocate_not_called (void *closure, void *ptr)
+{
+  FAIL_EXIT1 ("deallocate function called unexpectedly (%p, %p)",
+              closure, ptr);
+}
+
+/* Counter for various function calls.  */
+static int function_called;
+
+/* An allocation function which returns NULL and records that it has
+   been called.  */
+static void *
+allocate_return_null (void *closure)
+{
+  /* The function should only be called once.  */
+  TEST_COMPARE (function_called, 0);
+  ++function_called;
+  return NULL;
+}
+
+
+/* The following is used to check the retry logic, by causing a fake
+   race condition.  */
+static void *fake_race_place;
+static char fake_race_region[3]; /* To obtain unique addresses.  */
+
+static void *
+fake_race_allocate (void *closure)
+{
+  TEST_VERIFY (closure == &fake_race_region[0]);
+  TEST_COMPARE (function_called, 0);
+  ++function_called;
+  /* Fake allocation by another thread.  */
+  fake_race_place = &fake_race_region[1];
+  return &fake_race_region[2];
+}
+
+static void
+fake_race_deallocate (void *closure, void *ptr)
+{
+  /* Check that the pointer returned from fake_race_allocate is
+     deallocated (and not the one stored in fake_race_place).  */
+  TEST_VERIFY (ptr == &fake_race_region[2]);
+
+  TEST_VERIFY (fake_race_place == &fake_race_region[1]);
+  TEST_VERIFY (closure == &fake_race_region[0]);
+  TEST_COMPARE (function_called, 1);
+  ++function_called;
+}
+
+/* Similar to fake_race_allocate, but expects to be paired with free
+   as the deallocation function.  */
+static void *
+fake_race_allocate_for_free (void *closure)
+{
+  TEST_VERIFY (closure == &fake_race_region[0]);
+  TEST_COMPARE (function_called, 0);
+  ++function_called;
+  /* Fake allocation by another thread.  */
+  fake_race_place = &fake_race_region[1];
+  return xstrdup ("to be freed");
+}
+
+static int
+do_test (void)
+{
+  mtrace ();
+
+  /* Simple allocation.  */
+  void *place1 = NULL;
+  char *string1 = allocate_once (&place1, allocate_string,
+                                   deallocate_not_called,
+                                   (char *) "test string 1");
+  TEST_VERIFY_EXIT (string1 != NULL);
+  TEST_VERIFY (strcmp ("test string 1", string1) == 0);
+  /* Second call returns the first pointer, without calling any
+     callbacks.  */
+  TEST_VERIFY (string1
+               == allocate_once (&place1, allocate_not_called,
+                                 deallocate_not_called,
+                                 (char *) "test string 1a"));
+
+  /* Different place should result in another call.  */
+  void *place2 = NULL;
+  char *string2 = allocate_once (&place2, allocate_string,
+                                 deallocate_not_called,
+                                 (char *) "test string 2");
+  TEST_VERIFY_EXIT (string2 != NULL);
+  TEST_VERIFY (strcmp ("test string 2", string2) == 0);
+  TEST_VERIFY (string1 != string2);
+
+  /* Check error reporting (NULL return value from the allocation
+     function).  */
+  void *place3 = NULL;
+  char *string3 = allocate_once (&place3, allocate_return_null,
+                                 deallocate_not_called, NULL);
+  TEST_VERIFY (string3 == NULL);
+  TEST_COMPARE (function_called, 1);
+
+  /* Check that the deallocation function is called if the race is
+     lost.  */
+  function_called = 0;
+  TEST_VERIFY (allocate_once (&fake_race_place,
+                              fake_race_allocate,
+                              fake_race_deallocate,
+                              &fake_race_region[0])
+               == &fake_race_region[1]);
+  TEST_COMPARE (function_called, 2);
+  function_called = 3;
+  TEST_VERIFY (allocate_once (&fake_race_place,
+                              fake_race_allocate,
+                              fake_race_deallocate,
+                              &fake_race_region[0])
+               == &fake_race_region[1]);
+  TEST_COMPARE (function_called, 3);
+
+  /* Similar, but this time rely on that free is called.  */
+  function_called = 0;
+  fake_race_place = NULL;
+  TEST_VERIFY (allocate_once (&fake_race_place,
+                                fake_race_allocate_for_free,
+                                NULL,
+                                &fake_race_region[0])
+               == &fake_race_region[1]);
+  TEST_COMPARE (function_called, 1);
+  function_called = 3;
+  TEST_VERIFY (allocate_once (&fake_race_place,
+                              fake_race_allocate_for_free,
+                              NULL,
+                              &fake_race_region[0])
+               == &fake_race_region[1]);
+  TEST_COMPARE (function_called, 3);
+
+  free (place2);
+  free (place1);
+
+  return 0;
+}
+
+#include <support/test-driver.c>

The most recent patch looks good to me.

I have a minor comment for future patches:

On Fri, 2018-01-12 at 10:46 +0100, Florian Weimer wrote:
> +  while (true)
> +    {
> +      /* Synchronizes with the acquire MO load in allocate_once.  */
> +      void *expected = NULL;
> +      if (atomic_compare_exchange_weak_release (place, &expected, result))
> +        return result;
> +
> +      /* The failed CAS has relaxed MO semantics, so perform another
> +         acquire MO load.  */
> +      void *other_result = atomic_load_acquire (place);

You could just use expected here, because it has been updated, and ...

> +      if (other_result == NULL)
> +        /* Spurious failure.  Try again.  */
> +        continue;
> +
> +      /* We lost the race.  Free what we allocated and return the
> +         other result.  */

... add an atomic_thread_fence_acquire() here.

> +      if (deallocate == NULL)
> +        free (result);
> +      else
> +        deallocate (closure, result);
> +      return other_result;
> +    }

On 01/12/2018 12:47 PM, Torvald Riegel wrote:
> The most recent patch looks good to me.

Thanks!

> I have a minor comment for future patches:
> 
> On Fri, 2018-01-12 at 10:46 +0100, Florian Weimer wrote:
>> +  while (true)
>> +    {
>> +      /* Synchronizes with the acquire MO load in allocate_once.  */
>> +      void *expected = NULL;
>> +      if (atomic_compare_exchange_weak_release (place, &expected, result))
>> +        return result;
>> +
>> +      /* The failed CAS has relaxed MO semantics, so perform another
>> +         acquire MO load.  */
>> +      void *other_result = atomic_load_acquire (place);
> 
> You could just use expected here, because it has been updated, and ...
> 
>> +      if (other_result == NULL)
>> +        /* Spurious failure.  Try again.  */
>> +        continue;
>> +
>> +      /* We lost the race.  Free what we allocated and return the
>> +         other result.  */
> 
> ... add an atomic_thread_fence_acquire() here.

Isn't a an acquire MO load potentially cheaper than an acquire fence? 
The fence needs to synchronize with all threads, while the load only 
needs to synchronize with threads which have performed release MO store 
(or stronger) on the variable?

Florian

On Fri, 2018-01-12 at 13:40 +0100, Florian Weimer wrote:
> Isn't a an acquire MO load potentially cheaper than an acquire fence? 
> The fence needs to synchronize with all threads, while the load only 
> needs to synchronize with threads which have performed release MO store 
> (or stronger) on the variable?

It could be, potentially.  But that, of course, depends on the hardware
(eg, on x86, the acquire fence is really just a compiler barrier), and
currently the load will remain as a separate load even though it could
just be merged with the CAS (though that may change once GCC starts to
optimize atomics).

The best option here would be to use a CAS that has acquire MO on the
failure path, but we don't have that in atomic.h currently.  Even better
would be a strong version of that (which we don't have either,
currently).  But all of that doesn't matter much for the slow path,
which is where you use the CAS.

On Fri, Jan 12, 2018 at 10:46:31AM +0100, Florian Weimer wrote:
> +/* Allocate and initialize and object once, in a thread-safe fashion.
                              ^^^
I think you meant to say "an object".

Rich.

On 01/12/2018 03:33 PM, Richard W.M. Jones wrote:
> On Fri, Jan 12, 2018 at 10:46:31AM +0100, Florian Weimer wrote:
>> +/* Allocate and initialize and object once, in a thread-safe fashion.
>                                ^^^
> I think you meant to say "an object".

Thanks, fixed locally. 8-)

Florian