From patchwork Wed Sep 8 02:52:39 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Malte Skarupke X-Patchwork-Id: 44903 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 72E6D3858D35 for ; Wed, 8 Sep 2021 02:59:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 72E6D3858D35 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1631069945; bh=HQ2zqYkCUASjzgVAtVwAlcaikc1Pf7T/6aDnczsWJFc=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=qYs/+EwmLFHMp6tTpgUjGbZNrx2iAgEljuKqSSnuAj4nlli0VpDkfbNMQWWvGXoAn aCo5vp6xIWJ6hEtlKvuKRqLWz0D1bKrWrDFPTrDMwIwLPKRvXPl31xpqQFMxzJWx0D v6fe22KeSX7I++UoI3XUabVoziAPWgXiDyiTuevw= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mout.web.de (mout.web.de [212.227.17.12]) by sourceware.org (Postfix) with ESMTPS id 8EC5F38515E3 for ; Wed, 8 Sep 2021 02:54:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8EC5F38515E3 X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from auth2-smtp.messagingengine.com ([66.111.4.228]) by smtp.web.de (mrweb106 [213.165.67.124]) with ESMTPSA (Nemesis) id 1MMpCg-1mgZ250glw-00J18O; Wed, 08 Sep 2021 04:54:17 +0200 Received: from compute5.internal (compute5.nyi.internal [10.202.2.45]) by mailauth.nyi.internal (Postfix) with ESMTP id C8D5627C0064; Tue, 7 Sep 2021 22:54:15 -0400 (EDT) Received: from mailfrontend1 ([10.202.2.162]) by compute5.internal (MEProxy); Tue, 07 Sep 2021 22:54:15 -0400 X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvtddrudefiedgieduucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefhvffufffkofgjfhgggfestdekre dtredttdenucfhrhhomhepofgrlhhtvgcuufhkrghruhhpkhgvuceomhgrlhhtvghskhgr rhhuphhkvgesfigvsgdruggvqeenucggtffrrghtthgvrhhnpeevgfehffefffehleelie fftddvudffkedtkeduheeiueeugffgvdejgeduvdfgjeenucevlhhushhtvghrufhiiigv pedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehmrghlthgvshhkrghruhhpkhgvodhmvg hsmhhtphgruhhthhhpvghrshhonhgrlhhithihqddutddujedtfedvleeiqdduuddvgedv keeiledqmhgrlhhtvghskhgrrhhuphhkvgeppeifvggsrdguvgesfhgrshhtmhgrihhlrd hfmh X-ME-Proxy: Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 7 Sep 2021 22:54:15 -0400 (EDT) To: libc-alpha@sourceware.org Subject: [PATCH v2 6/6] nptl: Cleaning up __g1_start and related code in pthread_cond_wait Date: Tue, 7 Sep 2021 22:52:39 -0400 Message-Id: <20210908025239.1326480-7-malteskarupke@web.de> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20210908025239.1326480-1-malteskarupke@web.de> References: <20210908025239.1326480-1-malteskarupke@web.de> MIME-Version: 1.0 X-Provags-ID: V03:K1:xqMt/2VaYSSA/XPMqYuvQOaXo0cvtGA51BrH/6In4f5v30vRQBu wdPBKd689JBMCho3/hgcgr8CWIrgyxPaVN8rGuGDOesi036ZOW9kNQdGiGVCfNCYQSMFK3H lMRvQBUh9m3UT7gY38ETsyqZEdIT1o74TQMGWHpttbTGEnB4k17lKchXjmn/ycmer0shy4e fH+JQn+ifGoAOtOXy5fsA== X-UI-Out-Filterresults: notjunk:1;V03:K0:sINWOSAD9k4=:wlQQ5WsDnE/12GlNpIYKfK +w0MazdAR++d0ctztd1PEak5LlNk3vB7ogIWz6MdmtXxX+ZdgoapgkdNX2KoljGDwP4wObl5e g//sgzXr0wmxUKdw//21H9GJPVuP6Ua2HHTDcZYZNf9T0uh1FHm8jQ2T+lTV8TolUrR6/i3tT wTxP4TSX1WrJXYZuy+A6uat4jDgQaIYES1jnoYW3YsUpaRJrEovmd/BFnpD2BWmJWG24jDf93 4kZ+9ECeCUrxiBj2iOfMVJoGLbWkcbyAoI8jEeSxDtHQfUJIsAqiTmRMRRP5Q7BTZ7ny5o4cz +HVpxOq0EugmpqlRF7ou4fDDiuKobU1u00YPxiaIHtXkvZVHUuya8FzbHtNpXoMjxLRuu4J0D uWqY3yW6X22d45JaeXSSXSGY9Rz6HlmxapoIgaHPxXwbCUhj3P6v/aqEzcKJLXztwpSp+NYsG FpqOupHUqUa3KQpzBdbHBN1qScAeJLgIqPSIPaVz/9Sp4zL0bdzDKcz6Ulw9998e5NwPsFbYv vPgHbQ3zRkcNTm9A08O7e2E54QRjgsKgBv+bmIfgES7wa6WZKWz6QvMJe7oLktt+8F4yMut34 ZPe2HKHo3GaSt1fh3cWMw/0N7d+yIgBB+FycINw6DZv2LsZ1CUEHgG+hZ7m2kzmlGky8nZXDC 3scIgd+IY92q5TDzX6N7JR1/7BCHYCWc2fkblQtDB6s0QZKDbsO7zImHlEiQAIGRfqaaUo0NB QZJJjJd51cjXihJMx6Zmg4+3+M1yJxVBqMu6QI9R2bZQi2XuuVXLbQu6f+CKFSiNbORkblKZB H1/BDMW09L2K8+c8oi09hkfcph5K4K1UVBTfgV9jjCukO/NQrpYCb2cf/xYxMUWOHUBegVZYg ZLOWC1aeZp7HZi2Iv9AZfBCQTKFm4P40HkzWtBCy/WoI6URZGZDP83ZPORnyq9dKh1nGqX2BF aS8RLyCiUIXnObiZdBqQ0xafyYhaoHQ/vudPbGRh/lwMfvIvbFQa7rCNgizpFwcGuhez1M8Bk o+VaxlM8aYQxppoo8XmIbLZV6Yu0z2pTV0wtdFJIh2K/+rpDEwRsqfEAsjvcFRUoO50x8RZtj zbB//Zu5RliGYQgwjgViylEp6rERpBM17JfxNU6OYBjWPfHGgybwVhCAQ== X-Spam-Status: No, score=-13.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Malte Skarupke via Libc-alpha From: Malte Skarupke Reply-To: Malte Skarupke Cc: Malte Skarupke , triegel@redhat.com, malteskarupke@fastmail.fm Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" After my previous changes, __g1_start can be simpler. It can not change while a thread is in pthread_cond_wait, because groups are only allowed to switch when all threads in g1 have left that function. So there is no need to check if it has changed in pthread_cond_wait. After __g1_start was no longer read in pthread_cond_wait, it was only read in code that holds the internal lock of the condition variable. So there was no longer a need for __g1_start to be atomic. Finally, the low bit of __g1_start was only used in the block that's was supposed to handle potential stealing of signals. Since I deleted that block, we can stop shifting the count in __g1_start. --- nptl/pthread_cond_common.c | 71 ++++++------------------- nptl/pthread_cond_wait.c | 45 +++------------- sysdeps/nptl/bits/thread-shared-types.h | 10 +--- sysdeps/nptl/pthread.h | 2 +- 4 files changed, 27 insertions(+), 101 deletions(-) -- 2.25.1 diff --git a/nptl/pthread_cond_common.c b/nptl/pthread_cond_common.c index 9af6a6fbec..2d8cc7ca10 100644 --- a/nptl/pthread_cond_common.c +++ b/nptl/pthread_cond_common.c @@ -43,29 +43,16 @@ __condvar_fetch_xor_wseq_release (pthread_cond_t *cond, unsigned int val) return atomic_fetch_xor_release (&cond->__data.__wseq, val); } -static uint64_t __attribute__ ((unused)) -__condvar_load_g1_start_relaxed (pthread_cond_t *cond) -{ - return atomic_load_relaxed (&cond->__data.__g1_start); -} - -static void __attribute__ ((unused)) -__condvar_add_g1_start_relaxed (pthread_cond_t *cond, unsigned int val) -{ - atomic_store_relaxed (&cond->__data.__g1_start, - atomic_load_relaxed (&cond->__data.__g1_start) + val); -} - #else -/* We use two 64b counters: __wseq and __g1_start. They are monotonically - increasing and single-writer-multiple-readers counters, so we can implement - load, fetch-and-add, and fetch-and-xor operations even when we just have - 32b atomics. Values we add or xor are less than or equal to 1<<31 (*), - so we only have to make overflow-and-addition atomic wrt. to concurrent - load operations and xor operations. To do that, we split each counter into - two 32b values of which we reserve the MSB of each to represent an - overflow from the lower-order half to the higher-order half. +/* __wseq is a 64b counter. It is a monotonically increasing + single-writer-multiple-readers counter, so we can implement load, + fetch-and-add, and fetch-and-xor operations even when we just have 32b + atomics. Values we add or xor are less than or equal to 1<<31, so we only + have to make overflow-and-addition atomic wrt. to concurrent load + operations and xor operations. To do that, we split the counter into two + 32b values of which we reserve the MSB of each to represent an overflow + from the lower-order half to the higher-order half. In the common case, the state is (higher-order / lower-order half, and . is basically concatenation of the bits): @@ -104,11 +91,7 @@ __condvar_add_g1_start_relaxed (pthread_cond_t *cond, unsigned int val) can almost always interpret a snapshot of each halves. Readers can be forced to read a new snapshot when the read is concurrent with an overflow. However, overflows will happen infrequently, so load operations are - practically lock-free. - - (*) The highest value we add is __PTHREAD_COND_MAX_GROUP_SIZE << 2 to - __g1_start (the two extra bits are for the lock in the two LSBs of - __g1_start). */ + practically lock-free. */ typedef struct { @@ -228,20 +211,6 @@ __condvar_fetch_xor_wseq_release (pthread_cond_t *cond, unsigned int val) return ((uint64_t) h << 31) + l2; } -static uint64_t __attribute__ ((unused)) -__condvar_load_g1_start_relaxed (pthread_cond_t *cond) -{ - return __condvar_load_64_relaxed - ((_condvar_lohi *) &cond->__data.__g1_start32); -} - -static void __attribute__ ((unused)) -__condvar_add_g1_start_relaxed (pthread_cond_t *cond, unsigned int val) -{ - ignore_value (__condvar_fetch_add_64_relaxed - ((_condvar_lohi *) &cond->__data.__g1_start32, val)); -} - #endif /* !__HAVE_64B_ATOMICS */ @@ -350,7 +319,7 @@ __condvar_quiesce_and_switch_g1 (pthread_cond_t *cond, uint64_t wseq, behavior. Note that this works correctly for a zero-initialized condvar too. */ unsigned int old_orig_size = __condvar_get_orig_size (cond); - uint64_t old_g1_start = __condvar_load_g1_start_relaxed (cond) >> 1; + uint64_t old_g1_start = cond->__data.__g1_start; if (((unsigned) (wseq - old_g1_start - old_orig_size) + cond->__data.__g_size[g1 ^ 1]) == 0) return false; @@ -380,10 +349,10 @@ __condvar_quiesce_and_switch_g1 (pthread_cond_t *cond, uint64_t wseq, /* Wait until there are no group references anymore. The fetch-or operation injects us into the modification order of __g_refs; release MO ensures that waiters incrementing __g_refs after our fetch-or see the previous - changes to __g_signals and to __g1_start that had to happen before we can - switch this G1 and alias with an older group (we have two groups, so - aliasing requires switching group roles twice). Note that nobody else - can have set the wake-request flag, so we do not have to act upon it. + change to __g_signals that had to happen before we can switch this G1 + and alias with an older group (we have two groups, so aliasing requires + switching group roles twice). Note that nobody else can have set the + wake-request flag, so we do not have to act upon it. Also note that it is harmless if older waiters or waiters from this G1 get a group reference after we have quiesced the group because it will @@ -421,15 +390,9 @@ __condvar_quiesce_and_switch_g1 (pthread_cond_t *cond, uint64_t wseq, after the waiters we waited for. */ atomic_fetch_and_acquire (cond->__data.__g_refs + g1, ~(unsigned int)1); - /* Update __g1_start, which finishes closing this group. The value we add - will never be negative because old_orig_size can only be zero when we - switch groups the first time after a condvar was initialized, in which - case G1 will be at index 1 and we will add a value of 1. See above for - why this takes place after waiting for quiescence of the group. - Relaxed MO is fine because the change comes with no additional - constraints that others would have to observe. */ - __condvar_add_g1_start_relaxed (cond, - (old_orig_size << 1) + (g1 == 1 ? 1 : - 1)); + /* Update __g1_start, which finishes closing this group. See above for + why this takes place after waiting for quiescence of the group. */ + cond->__data.__g1_start += old_orig_size; /* Now reopen the group, thus enabling waiters to again block using the futex controlled by __g_signals. Release MO so that observers that see diff --git a/nptl/pthread_cond_wait.c b/nptl/pthread_cond_wait.c index b833e543a5..939d3e9b69 100644 --- a/nptl/pthread_cond_wait.c +++ b/nptl/pthread_cond_wait.c @@ -72,7 +72,7 @@ __condvar_cancel_waiting (pthread_cond_t *cond, uint64_t seq, unsigned int g, not hold a reference on the group. */ __condvar_acquire_lock (cond, private); - uint64_t g1_start = __condvar_load_g1_start_relaxed (cond) >> 1; + uint64_t g1_start = cond->__data.__g1_start; if (g1_start > seq) { /* Our group is closed, so someone provided enough signals for it. @@ -275,9 +275,8 @@ __condvar_cleanup_waiting (void *arg) * Waiters fetch-add while having acquire the mutex associated with the condvar. Signalers load it and fetch-xor it concurrently. __g1_start: Starting position of G1 (inclusive) - * LSB is index of current G2. - * Modified by signalers while having acquired the condvar-internal lock - and observed concurrently by waiters. + * Modified by signalers and observed by waiters, both only while having + acquired the condvar-internal lock. __g1_orig_size: Initial size of G1 * The two least-significant bits represent the condvar-internal lock. * Only accessed while having acquired the condvar-internal lock. @@ -314,16 +313,6 @@ __condvar_cleanup_waiting (void *arg) A PTHREAD_COND_INITIALIZER condvar has all fields set to zero, which yields a condvar that has G2 starting at position 0 and a G1 that is closed. - Because waiters do not claim ownership of a group right when obtaining a - position in __wseq but only reference count the group when using futexes - to block, it can happen that a group gets closed before a waiter can - increment the reference count. Therefore, waiters have to check whether - their group is already closed using __g1_start. They also have to perform - this check when spinning when trying to grab a signal from __g_signals. - Note that for these checks, using relaxed MO to load __g1_start is - sufficient because if a waiter can see a sufficiently large value, it could - have also consume a signal in the waiters group. - It is essential that the last field in pthread_cond_t is __g_signals[1]: The previous condvar used a pointer-sized field in pthread_cond_t, so a PTHREAD_COND_INITIALIZER from that condvar implementation might only @@ -415,8 +404,7 @@ __pthread_cond_wait_common (pthread_cond_t *cond, pthread_mutex_t *mutex, /* Now wait until a signal is available in our group or it is closed. Acquire MO so that if we observe a value of zero written after group switching in __condvar_quiesce_and_switch_g1, we synchronize with that - store and will see the prior update of __g1_start done while switching - groups too. */ + store. */ unsigned int signals = atomic_load_acquire (cond->__data.__g_signals + g); do @@ -436,11 +424,6 @@ __pthread_cond_wait_common (pthread_cond_t *cond, pthread_mutex_t *mutex, unsigned int spin = maxspin; while (signals == 0 && spin > 0) { - /* Check that we are not spinning on a group that's already - closed. */ - if (seq < (__condvar_load_g1_start_relaxed (cond) >> 1)) - goto done; - /* TODO Back off. */ /* Reload signals. See above for MO. */ @@ -457,19 +440,7 @@ __pthread_cond_wait_common (pthread_cond_t *cond, pthread_mutex_t *mutex, if (signals != 0) break; - /* No signals available after spinning, so prepare to block. - First check the closed flag on __g_signals that designates a - concurrent attempt to reuse the group's slot. We use acquire MO for - the __g_signals check to make sure we read the current value of - __g1_start (see above). */ - if (((atomic_load_acquire (cond->__data.__g_signals + g) & 1) != 0) - || (seq < (__condvar_load_g1_start_relaxed (cond) >> 1))) - { - /* Our group is closed. */ - goto done; - } - - // Now block. + // No signals available after spinning, so block. struct _pthread_cleanup_buffer buffer; struct _condvar_cleanup_buffer cbuffer; cbuffer.wseq = wseq; @@ -501,9 +472,9 @@ __pthread_cond_wait_common (pthread_cond_t *cond, pthread_mutex_t *mutex, } } - /* Try to grab a signal. Use acquire MO so that we see an up-to-date value - of __g1_start when spinning above. */ - while (!atomic_compare_exchange_weak_acquire (cond->__data.__g_signals + g, + /* Try to grab a signal. Relaxed MO is enough because the group can't be + closed while we're in this loop, so there are no writes we could miss. */ + while (!atomic_compare_exchange_weak_relaxed (cond->__data.__g_signals + g, &signals, signals - 2)); done: diff --git a/sysdeps/nptl/bits/thread-shared-types.h b/sysdeps/nptl/bits/thread-shared-types.h index 494a43a675..cec88694ca 100644 --- a/sysdeps/nptl/bits/thread-shared-types.h +++ b/sysdeps/nptl/bits/thread-shared-types.h @@ -100,15 +100,7 @@ struct __pthread_cond_s unsigned int __high; } __wseq32; }; - __extension__ union - { - __extension__ unsigned long long int __g1_start; - struct - { - unsigned int __low; - unsigned int __high; - } __g1_start32; - }; + unsigned long long int __g1_start; unsigned int __g_refs[2] __LOCK_ALIGNMENT; unsigned int __g_size[2]; unsigned int __g1_orig_size; diff --git a/sysdeps/nptl/pthread.h b/sysdeps/nptl/pthread.h index f1b7f2bdc6..324a2d7659 100644 --- a/sysdeps/nptl/pthread.h +++ b/sysdeps/nptl/pthread.h @@ -152,7 +152,7 @@ enum /* Conditional variable handling. */ -#define PTHREAD_COND_INITIALIZER { { {0}, {0}, {0, 0}, {0, 0}, 0, 0, {0, 0} } } +#define PTHREAD_COND_INITIALIZER { { {0}, 0, {0, 0}, {0, 0}, 0, 0, {0, 0} } } /* Cleanup buffers */