From patchwork Tue Jan 9 20:07:32 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Florian Weimer X-Patchwork-Id: 857706 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=sourceware.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=libc-alpha-return-88984-incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.b="FY2fK25k"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3zGNW41pd3z9s7M for ; Wed, 10 Jan 2018 07:08:32 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:subject:from:to:cc:references:message-id:date :mime-version:in-reply-to:content-type; q=dns; s=default; b=LY3L pItsXpjm6RYWgeHU7fyAdtABpmg1TfZ5jJGSrAOlecPLyIGfUBOry7jor6I8V+dM Covh3aQmUTTjFKVZtrEMbVIV/fxnahW50XZGcmseB92VT/9yaeJE4RfqbJ5zhVkP uUzod2ECiQdOtzGccGYaqA/Zn610ndJZfPGbZPA= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:subject:from:to:cc:references:message-id:date :mime-version:in-reply-to:content-type; s=default; bh=kyQLLmL1EL 4d8YSVvl9/wE9p7FY=; b=FY2fK25kk+s4Br6YnYCRjCVhNrIYhbsYx+eNxJSUCP 0jij6cdxo5Sl11v0dVoUXvKgQy5qMpBfY98uBVtMrME0hZSizAC4u/0p+R73l8Ne UNURUesMM4YxtGDpAvQ51ypgFL4hS4Mgf0nWkUWHONVgbTsnN1Cy0DyZZPIoByrf c= Received: (qmail 109803 invoked by alias); 9 Jan 2018 20:07:50 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 109729 invoked by uid 89); 9 Jan 2018 20:07:46 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, SPF_HELO_PASS, T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=yielding, ALLOCATE X-HELO: mx1.redhat.com Subject: [PATCH] Implement allocate_once (was: Re: [PATCH] Implement libc_once_retry for atomic initialization with allocation) From: Florian Weimer To: Torvald Riegel Cc: GNU C Library , "Dmitry V. Levin" References: <6e4b6b22-3f38-f798-f2e0-eb22311ed6b5@redhat.com> <1515086144.9480.286.camel@redhat.com> <2d12ba41-e3ff-70db-484e-19d9805c5e53@redhat.com> <1515090825.9480.295.camel@redhat.com> <267148c7-61c9-b45b-7533-96284cae5e7d@redhat.com> Message-ID: <8a260297-4aaa-2a04-776a-cb5cbbb1fdf0@redhat.com> Date: Tue, 9 Jan 2018 21:07:32 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.5.0 MIME-Version: 1.0 In-Reply-To: <267148c7-61c9-b45b-7533-96284cae5e7d@redhat.com> 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 Subject: [PATCH] Implement allocate_once for atomic initialization with allocation To: libc-alpha@sourceware.org 2018-01-04 Florian Weimer 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 + . */ + +#ifndef _ALLOCATE_ONCE_H +#define _ALLOCATE_ONCE_H + +#include + +/* 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 + . */ + +#include +#include +#include + +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 + . */ + +#include +#include +#include +#include + +/* 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