Message ID | 6e4b6b22-3f38-f798-f2e0-eb22311ed6b5@redhat.com |
---|---|
State | New |
Headers | show |
Series | Implement libc_once_retry for atomic initialization with allocation | expand |
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.
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
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).
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 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>
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.
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.
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 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>
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>