[PATCH] Implement libc_once_retry for atomic initialization with allocation

[PATCH] Implement libc_once_retry for atomic initialization with allocation

[Florian Weimer]

[-- Attachment #1: Type: text/plain, Size: 208 bytes --]

I'd appreciate if we could add this even during the freeze because it 
helps me to write a bug fix (but I guess I could use __libc_once there).

Torvald, does the algorithm look okay to you?

Thanks,
Florian

[-- Attachment #2: lor.patch --]
[-- Type: text/x-patch, Size: 12186 bytes --]

Subject: [PATCH] Implement libc_once_retry for atomic initialization with allocation
To: libc-alpha@sourceware.org

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

	* include/atomic.h (__libc_once_retry_slow): Declare.
	(libc_once_retry): Define.
	* misc/libc_once_retry.c: New file.
	* misc/tst-libc_once_retry.c: Likewise.
	* misc/Makefile (routines): Add libc_once_retry.
	(tests-internal): Add tst-libc_once_retry.
	* misc/Versions (GLIBC_PRIVATE): Add __libc_once_retry_slow.

diff --git a/include/atomic.h b/include/atomic.h
index 6af07dba58..91e176b040 100644
--- a/include/atomic.h
+++ b/include/atomic.h
@@ -826,4 +826,58 @@ void __atomic_link_error (void);
 # error ATOMIC_EXCHANGE_USES_CAS has to be defined.
 #endif
 
+/* Slow path for libc_once_retry; see below.  */
+void *__libc_once_retry_slow (void **__place,
+			      void *(*__allocate) (void *__closure),
+			      void (*__deallocate) (void *__closure,
+						    void *__ptr),
+			      void *__closure);
+
+/* Perform an acquire MO load on *PLACE.  If *PLACE is not NULL,
+   return *PLACE.  Otherwise, call ALLOCATE (CLOSURE).  If that
+   returns NULL, return NULL.  Otherwise, atomically replace *PLACE
+   with PTR, the result of the ALLOCATE call (with acquire-release
+   MO).  If *PLACE was updated concurrently, call DEALLOCATE (CLOSURE,
+   PTR) to undo the effect of allocate, and return the new value of
+   *PLACE.  If DEALLOCATE is NULL, call the free (PTR) instead.
+
+   It is expected that callers define an inline helper function
+   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 __libc_once_retry (&global_foo, allocate_foo, free_foo, NULL);
+   }
+
+   Usage of this function looks like this:
+
+   struct foo *local_foo = get_foo ();
+   if (local_foo == NULL)
+      report_allocation_failure ();
+
+   Compare to __libc_once, __libc_once_retry 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 provided callback functions are safe.  */
+static inline void *
+libc_once_retry (void **__place, void *(*__allocate) (void *__closure),
+		 void (*__deallocate) (void *__closure, void *__ptr),
+		 void *__closure)
+{
+  /* Synchronizes with the release-store CAS in
+     __libc_once_retry_slow.  */
+  void *__result = atomic_load_acquire (__place);
+  if (__result != NULL)
+    return __result;
+  else
+    return __libc_once_retry_slow (__place, __allocate, __deallocate,
+				   __closure);
+}
+
 #endif	/* atomic.h */
diff --git a/misc/Makefile b/misc/Makefile
index a5076b3672..7b1314d01b 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 \
+	    libc_once_retry
 
 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-libc_once_retry
 tests-static := tst-empty
 
 ifeq ($(run-built-tests),yes)
diff --git a/misc/Versions b/misc/Versions
index bfbda505e4..a129e90fc0 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_once_retry_slow;
   }
 }
diff --git a/misc/libc_once_retry.c b/misc/libc_once_retry.c
new file mode 100644
index 0000000000..ecd352e2a3
--- /dev/null
+++ b/misc/libc_once_retry.c
@@ -0,0 +1,55 @@
+/* Concurrent 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 <atomic.h>
+#include <stdlib.h>
+
+void *
+__libc_once_retry_slow (void **place, void *(*allocate) (void *closure),
+                        void (*deallocate) (void *closure, void *ptr),
+                        void *closure)
+{
+  void *result;
+
+  do
+    {
+      result = allocate (closure);
+      if (result == NULL)
+        return NULL;
+
+      /* Synchronizes with the acquire MO load in
+         __libc_once_retry.  */
+      void *expected = NULL;
+      if (atomic_compare_exchange_weak_release (place, &expected, result))
+        return result;
+
+      /* We lost the race.  Free our value.  */
+      if (deallocate == NULL)
+        free (result);
+      else
+        deallocate (closure, result);
+
+      /* The failed CAS has relaxed MO semantics, so perform another
+         acquire MO load.  */
+      result = atomic_load_acquire (place);
+
+      /* Loop around in case of a spurious CAS failure.  */
+    } while (result == NULL);
+
+  return result;
+}
diff --git a/misc/tst-libc_once_retry.c b/misc/tst-libc_once_retry.c
new file mode 100644
index 0000000000..5dedd21964
--- /dev/null
+++ b/misc/tst-libc_once_retry.c
@@ -0,0 +1,175 @@
+/* Test the libc_once_retry 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 <atomic.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)
+{
+  /* Simple allocation.  */
+  void *place1 = NULL;
+  char *string1 = libc_once_retry (&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
+               == libc_once_retry (&place1, allocate_not_called,
+                                   deallocate_not_called,
+                                   (char *) "test string 1a"));
+
+  /* Difference place should result in another call.  */
+  void *place2 = NULL;
+  char *string2 = libc_once_retry (&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 = libc_once_retry (&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 (libc_once_retry (&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 (libc_once_retry (&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 (libc_once_retry (&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 (libc_once_retry (&fake_race_place,
+                                fake_race_allocate_for_free,
+                                NULL,
+                                &fake_race_region[0])
+               == &fake_race_region[1]);
+  TEST_COMPARE (function_called, 3);
+
+  return 0;
+}
+
+#include <support/test-driver.c>

Re: [PATCH] Implement libc_once_retry for atomic initialization with allocation

[Andreas Schwab]

On Jan 04 2018, Florian Weimer <fweimer@redhat.com> wrote:

> +   static inline struct foo *
> +   get_foo (void)
> +   {
> +     return __libc_once_retry (&global_foo, allocate_foo, free_foo, NULL);

s/__//

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [PATCH] Implement libc_once_retry for atomic initialization with allocation

[Florian Weimer]

On 01/04/2018 04:15 PM, Andreas Schwab wrote:
> On Jan 04 2018, Florian Weimer <fweimer@redhat.com> wrote:
> 
>> +   static inline struct foo *
>> +   get_foo (void)
>> +   {
>> +     return __libc_once_retry (&global_foo, allocate_foo, free_foo, NULL);
> 
> s/__//

Thanks, fixed locally.

Florian

Re: [PATCH] Implement libc_once_retry for atomic initialization with allocation

[Torvald Riegel]

On Thu, 2018-01-04 at 16:09 +0100, Florian Weimer wrote:
> Subject: [PATCH] Implement libc_once_retry for atomic initialization with allocation

Can you find a different name for it?  It has similarities to a generic
libc_once, but the pattern is more special.

Do you need it often enough to make it worth breaking it out?

> diff --git a/include/atomic.h b/include/atomic.h
> index 6af07dba58..91e176b040 100644
> --- a/include/atomic.h
> 
> +++ b/include/atomic.h

I don't think this should go into atomic.h because this is where we
really handle the basics of synchronization.  This is a synchronization
helper, and doesn't need to be touched by someone porting glibc to
another arch.

> @@ -826,4 +826,58 @@ void __atomic_link_error (void);
>  # error ATOMIC_EXCHANGE_USES_CAS has to be defined.
>  #endif
>  
> +/* Slow path for libc_once_retry; see below.  */
> 
> +void *__libc_once_retry_slow (void **__place,
> 
> +			      void *(*__allocate) (void *__closure),
> 
> +			      void (*__deallocate) (void *__closure,
> 
> +						    void *__ptr),
> 
> +			      void *__closure);
> 
> +
> 
> +/* Perform an acquire MO load on *PLACE.  If *PLACE is not NULL,
> 
> +   return *PLACE.  Otherwise, call ALLOCATE (CLOSURE).  If that
> 
> +   returns NULL, return NULL.  Otherwise, atomically replace *PLACE
> 
> +   with PTR, the result of the ALLOCATE call (with acquire-release

That doesn't quite match what you implement.  First, you don't replace
it unconditionally, but use a CAS (you can't just throw in an
"atomically" here because the allocations are mixed in and they aren't).
Second, you use the weak CAS but the loop includes alloc/dealloc; see
below.

> +   MO).  If *PLACE was updated concurrently, call DEALLOCATE (CLOSURE,
> 
> +   PTR) to undo the effect of allocate, and return the new value of
> 
> +   *PLACE.  If DEALLOCATE is NULL, call the free (PTR) instead.

s/the //

> 
> +
> 
> +   It is expected that callers define an inline helper function
> 
> +   function which adds type safety, like this.

s/function function which/function that/
s/./:/

> 
> +
> 
> +   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 __libc_once_retry (&global_foo, allocate_foo, free_foo, NULL);
> 
> +   }
> 
> +
> 
> +   Usage of this function looks like this:
> 
> +
> 
> +   struct foo *local_foo = get_foo ();
> 
> +   if (local_foo == NULL)
> 
> +      report_allocation_failure ();
> 
> +
> 
> +   Compare to __libc_once, __libc_once_retry has the advantage that it

Compare_d_

> +   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 provided callback functions are safe.  */
> 
> +static inline void *
> 
> +libc_once_retry (void **__place, void *(*__allocate) (void *__closure),
> 
> +		 void (*__deallocate) (void *__closure, void *__ptr),
> 
> +		 void *__closure)
> 
> +{
> 
> +  /* Synchronizes with the release-store CAS in

s/release-store/release MO/

> diff --git a/misc/libc_once_retry.c b/misc/libc_once_retry.c
> new file mode 100644
> index 0000000000..ecd352e2a3
> --- /dev/null
> 
> +++ b/misc/libc_once_retry.c
> 
> @@ -0,0 +1,55 @@
> +/* Concurrent 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 <atomic.h>
> 
> +#include <stdlib.h>
> 
> +
> 
> +void *
> 
> +__libc_once_retry_slow (void **place, void *(*allocate) (void *closure),
> 
> +                        void (*deallocate) (void *closure, void *ptr),
> 
> +                        void *closure)
> 
> +{
> 
> +  void *result;
> 
> +
> 
> +  do
> 
> +    {
> 
> +      result = allocate (closure);
> 
> +      if (result == NULL)
> 
> +        return NULL;
> 
> +
> 
> +      /* Synchronizes with the acquire MO load in
> 
> +         __libc_once_retry.  */
> 
> +      void *expected = NULL;
> 
> +      if (atomic_compare_exchange_weak_release (place, &expected, result))
> 
> +        return result;

It seems you're looking for a strong CAS here, so why don't you make a
loop around the weak CAS?  Using an acq_rel CAS, this is simpler.

You'd avoid having more than one allocate/deallocate pair, which might
be unexpected given that you're documentation of the function's
semantics doesn't make that clear (and it might perhaps matter for
custom alloc/dealloc functions).

Re: [PATCH] Implement libc_once_retry for atomic initialization with allocation

[Florian Weimer]

[-- Attachment #1: Type: text/plain, Size: 3346 bytes --]

On 01/04/2018 06:15 PM, Torvald Riegel wrote:
> On Thu, 2018-01-04 at 16:09 +0100, Florian Weimer wrote:
>> Subject: [PATCH] Implement libc_once_retry for atomic initialization with allocation
> 
> Can you find a different name for it?  It has similarities to a generic
> libc_once, but the pattern is more special.

libc_concurrent_init?

> Do you need it often enough to make it worth breaking it out?

I think it's worthwhile to separate the concurrency review from the 
application logic.

>> diff --git a/include/atomic.h b/include/atomic.h
>> index 6af07dba58..91e176b040 100644
>> --- a/include/atomic.h
>>
>> +++ b/include/atomic.h
> 
> I don't think this should go into atomic.h because this is where we
> really handle the basics of synchronization.  This is a synchronization
> helper, and doesn't need to be touched by someone porting glibc to
> another arch.

What would be a good place instead?  A new header file?

>> +/* Perform an acquire MO load on *PLACE.  If *PLACE is not NULL,
>>
>> +   return *PLACE.  Otherwise, call ALLOCATE (CLOSURE).  If that
>>
>> +   returns NULL, return NULL.  Otherwise, atomically replace *PLACE
>>
>> +   with PTR, the result of the ALLOCATE call (with acquire-release
> 
> That doesn't quite match what you implement.  First, you don't replace
> it unconditionally, but use a CAS (you can't just throw in an
> "atomically" here because the allocations are mixed in and they aren't).
> Second, you use the weak CAS but the loop includes alloc/dealloc; see
> below.

Hmm, right, that is unnecessary.  I have updated the comment in the 
attached patch.

/* 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
    turns out that *PLACE was updated concurrently, call DEALLOCATE
    (CLOSURE, RESULT) to undo the effect of ALLOCATE, and return the
    new value of *PLACE (after an acquire MO load).  If DEALLOCATE is
    NULL, call free (RESULT) instead.

    The net effect is that if libc_once_retry returns a non-NULL value,
    the caller can assume that pointed-to data has been initialized
    according to the ALLOCATE function.

>> +  do
>>
>> +    {
>>
>> +      result = allocate (closure);
>>
>> +      if (result == NULL)
>>
>> +        return NULL;
>>
>> +
>>
>> +      /* Synchronizes with the acquire MO load in
>>
>> +         __libc_once_retry.  */
>>
>> +      void *expected = NULL;
>>
>> +      if (atomic_compare_exchange_weak_release (place, &expected, result))
>>
>> +        return result;
> 
> It seems you're looking for a strong CAS here, so why don't you make a
> loop around the weak CAS?  Using an acq_rel CAS, this is simpler.

It's the only CAS we have: weak with relaxed MO on failure.  I need 
strong with acquire MO on failure, and currently, the only way to get 
that is with the loop and the additional load.  Sorry.

> You'd avoid having more than one allocate/deallocate pair, which might
> be unexpected given that you're documentation of the function's
> semantics doesn't make that clear (and it might perhaps matter for
> custom alloc/dealloc functions).

Oh, good point.  I changed the implementation in the attached patch.

Thanks,
Florian

[-- Attachment #2: lor2.patch --]
[-- Type: text/x-patch, Size: 12502 bytes --]

Subject: [PATCH] Implement libc_once_retry for atomic initialization with allocation
To: libc-alpha@sourceware.org

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

	* include/atomic.h (__libc_once_retry_slow): Declare.
	(libc_once_retry): Define.
	* misc/libc_once_retry.c: New file.
	* misc/tst-libc_once_retry.c: Likewise.
	* misc/Makefile (routines): Add libc_once_retry.
	(tests-internal): Add tst-libc_once_retry.
	* misc/Versions (GLIBC_PRIVATE): Add __libc_once_retry_slow.

diff --git a/include/atomic.h b/include/atomic.h
index 6af07dba58..ec996cd224 100644
--- a/include/atomic.h
+++ b/include/atomic.h
@@ -826,4 +826,63 @@ void __atomic_link_error (void);
 # error ATOMIC_EXCHANGE_USES_CAS has to be defined.
 #endif
 
+/* Slow path for libc_once_retry; see below.  */
+void *__libc_once_retry_slow (void **__place,
+			      void *(*__allocate) (void *__closure),
+			      void (*__deallocate) (void *__closure,
+						    void *__ptr),
+			      void *__closure);
+
+/* 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
+   turns out that *PLACE was updated concurrently, call DEALLOCATE
+   (CLOSURE, RESULT) to undo the effect of ALLOCATE, and return the
+   new value of *PLACE (after an acquire MO load).  If DEALLOCATE is
+   NULL, call free (RESULT) instead.
+
+   The net effect is that if libc_once_retry 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 libc_once_retry (&global_foo, allocate_foo, free_foo, NULL);
+   }
+
+   Usage of this function looks like this:
+
+   struct foo *local_foo = get_foo ();
+   if (local_foo == NULL)
+      report_allocation_failure ();
+
+   Compared to __libc_once, __libc_once_retry 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 provided callback functions are safe.  */
+static inline void *
+libc_once_retry (void **__place, void *(*__allocate) (void *__closure),
+		 void (*__deallocate) (void *__closure, void *__ptr),
+		 void *__closure)
+{
+  /* Synchronizes with the release MO CAS in
+     __libc_once_retry_slow.  */
+  void *__result = atomic_load_acquire (__place);
+  if (__result != NULL)
+    return __result;
+  else
+    return __libc_once_retry_slow (__place, __allocate, __deallocate,
+				   __closure);
+}
+
 #endif	/* atomic.h */
diff --git a/misc/Makefile b/misc/Makefile
index a5076b3672..7b1314d01b 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 \
+	    libc_once_retry
 
 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-libc_once_retry
 tests-static := tst-empty
 
 ifeq ($(run-built-tests),yes)
diff --git a/misc/Versions b/misc/Versions
index bfbda505e4..a129e90fc0 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_once_retry_slow;
   }
 }
diff --git a/misc/libc_once_retry.c b/misc/libc_once_retry.c
new file mode 100644
index 0000000000..91c486975a
--- /dev/null
+++ b/misc/libc_once_retry.c
@@ -0,0 +1,57 @@
+/* Concurrent 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 <atomic.h>
+#include <stdlib.h>
+#include <stdbool.h>
+
+void *
+__libc_once_retry_slow (void **place, void *(*allocate) (void *closure),
+                        void (*deallocate) (void *closure, void *ptr),
+                        void *closure)
+{
+  void *result = allocate (closure);
+  if (result == NULL)
+    return NULL;
+
+  while (true)
+    {
+      /* Synchronizes with the acquire MO load in
+         __libc_once_retry.  */
+      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;
+}
diff --git a/misc/tst-libc_once_retry.c b/misc/tst-libc_once_retry.c
new file mode 100644
index 0000000000..9b2bbd187c
--- /dev/null
+++ b/misc/tst-libc_once_retry.c
@@ -0,0 +1,175 @@
+/* Test the libc_once_retry 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 <atomic.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)
+{
+  /* Simple allocation.  */
+  void *place1 = NULL;
+  char *string1 = libc_once_retry (&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
+               == libc_once_retry (&place1, allocate_not_called,
+                                   deallocate_not_called,
+                                   (char *) "test string 1a"));
+
+  /* Difference place should result in another call.  */
+  void *place2 = NULL;
+  char *string2 = libc_once_retry (&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 = libc_once_retry (&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 (libc_once_retry (&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 (libc_once_retry (&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 (libc_once_retry (&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 (libc_once_retry (&fake_race_place,
+                                fake_race_allocate_for_free,
+                                NULL,
+                                &fake_race_region[0])
+               == &fake_race_region[1]);
+  TEST_COMPARE (function_called, 3);
+
+  return 0;
+}
+
+#include <support/test-driver.c>

Re: [PATCH] Implement libc_once_retry for atomic initialization with allocation

[Torvald Riegel]

On Thu, 2018-01-04 at 18:44 +0100, Florian Weimer wrote:
> On 01/04/2018 06:15 PM, Torvald Riegel wrote:
> > On Thu, 2018-01-04 at 16:09 +0100, Florian Weimer wrote:
> >> Subject: [PATCH] Implement libc_once_retry for atomic initialization with allocation
> > 
> > Can you find a different name for it?  It has similarities to a generic
> > libc_once, but the pattern is more special.
> 
> libc_concurrent_init?

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.

> > Do you need it often enough to make it worth breaking it out?
> 
> I think it's worthwhile to separate the concurrency review from the 
> application logic.

That can be helpful, but making a generic helper for special cases (if
it's indeed one...) also has consts. 

> >> diff --git a/include/atomic.h b/include/atomic.h
> >> index 6af07dba58..91e176b040 100644
> >> --- a/include/atomic.h
> >>
> >> +++ b/include/atomic.h
> > 
> > I don't think this should go into atomic.h because this is where we
> > really handle the basics of synchronization.  This is a synchronization
> > helper, and doesn't need to be touched by someone porting glibc to
> > another arch.
> 
> What would be a good place instead?  A new header file?

I think so.  I'm not too keen on fine-granular headers usually, but
atomics and what we build on top of them is worth separating IMO.

> >> +/* Perform an acquire MO load on *PLACE.  If *PLACE is not NULL,
> >>
> >> +   return *PLACE.  Otherwise, call ALLOCATE (CLOSURE).  If that
> >>
> >> +   returns NULL, return NULL.  Otherwise, atomically replace *PLACE
> >>
> >> +   with PTR, the result of the ALLOCATE call (with acquire-release
> > 
> > That doesn't quite match what you implement.  First, you don't replace
> > it unconditionally, but use a CAS (you can't just throw in an
> > "atomically" here because the allocations are mixed in and they aren't).
> > Second, you use the weak CAS but the loop includes alloc/dealloc; see
> > below.
> 
> Hmm, right, that is unnecessary.  I have updated the comment in the 
> attached patch.
> 
> /* 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. 

>     turns out that *PLACE was updated concurrently, call DEALLOCATE
>     (CLOSURE, RESULT) to undo the effect of ALLOCATE, and return the
>     new value of *PLACE (after an acquire MO load).  If DEALLOCATE is
>     NULL, call free (RESULT) instead.
> 
>     The net effect is that if libc_once_retry returns a non-NULL value,
>     the caller can assume that pointed-to data has been initialized
>     according to the ALLOCATE function.

That's a useful addition, and might even be the first sentence :)

> >> +  do
> >>
> >> +    {
> >>
> >> +      result = allocate (closure);
> >>
> >> +      if (result == NULL)
> >>
> >> +        return NULL;
> >>
> >> +
> >>
> >> +      /* Synchronizes with the acquire MO load in
> >>
> >> +         __libc_once_retry.  */
> >>
> >> +      void *expected = NULL;
> >>
> >> +      if (atomic_compare_exchange_weak_release (place, &expected, result))
> >>
> >> +        return result;
> > 
> > It seems you're looking for a strong CAS here, so why don't you make a
> > loop around the weak CAS?  Using an acq_rel CAS, this is simpler.
> 
> It's the only CAS we have: weak with relaxed MO on failure.  I need 
> strong with acquire MO on failure, and currently, the only way to get 
> that is with the loop and the additional load.  Sorry.

That's fine.  The strong CAS is really simple to do with a weak CAS if
one ignores back-off.

Re: [PATCH] Implement libc_once_retry for atomic initialization with allocation

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 302 bytes --]

On Thu, Jan 04, 2018 at 04:09:43PM +0100, Florian Weimer wrote:
> I'd appreciate if we could add this even during the freeze because it 
> helps me to write a bug fix (but I guess I could use __libc_once there).

Yes, I think we can add a symbol to GLIBC_PRIVATE during soft freeze.


-- 
ldv

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

Re: [PATCH] Implement libc_once_retry for atomic initialization with allocation

[Florian Weimer]

[-- Attachment #1: Type: text/plain, Size: 890 bytes --]

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.

Thanks,
Florian

[-- Attachment #2: lor3.patch --]
[-- Type: text/x-patch, Size: 13928 bytes --]

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..af07f9b614
--- /dev/null
+++ b/include/allocate_once.h
@@ -0,0 +1,88 @@
+/* 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.  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);
+  if (__result != NULL)
+    return __result;
+  else
+    return __libc_allocate_once_slow (__place, __allocate, __deallocate,
+                                      __closure);
+}
+
+#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
 
 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
 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;
   }
 }
diff --git a/misc/allocate_once.c b/misc/allocate_once.c
new file mode 100644
index 0000000000..9353bd828f
--- /dev/null
+++ b/misc/allocate_once.c
@@ -0,0 +1,58 @@
+/* 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 <atomic.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;
+}
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);
+}
+
+/* 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)
+{
+  /* 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"));
+
+  /* Difference 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);
+
+  return 0;
+}
+
+#include <support/test-driver.c>

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

[Florian Weimer]

[-- Attachment #1: Type: text/plain, Size: 1074 bytes --]

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

[-- Attachment #2: lor4.patch --]
[-- Type: text/x-patch, Size: 14054 bytes --]

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.
+   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.  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);
+  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
 
 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
 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;
   }
 }
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..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);
+}
+
+/* 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)
+{
+  /* 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"));
+
+  /* Difference 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);
+
+  return 0;
+}
+
+#include <support/test-driver.c>

Re: [PATCH] Implement allocate_once

[Carlos O'Donell]

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>


-- 
Cheers,
Carlos.

Re: [PATCH] Implement allocate_once

[Florian Weimer]

[-- Attachment #1: Type: text/plain, Size: 318 bytes --]

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

[-- Attachment #2: lor5.patch --]
[-- Type: text/x-patch, Size: 15305 bytes --]

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>

Re: [PATCH] Implement allocate_once

[Torvald Riegel]

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;
> +    }

Re: [PATCH] Implement allocate_once

[Florian Weimer]

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

Re: [PATCH] Implement allocate_once

[Torvald Riegel]

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.

Re: [PATCH] Implement allocate_once

[Richard W.M. Jones]

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.

-- 
Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones
Read my programming and virtualization blog: http://rwmj.wordpress.com
virt-top is 'top' for virtual machines.  Tiny program with many
powerful monitoring features, net stats, disk stats, logging, etc.
http://people.redhat.com/~rjones/virt-top

Re: [PATCH] Implement allocate_once

[Florian Weimer]

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