From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI autolearn=ham autolearn_force=no version=3.4.4 Received: from second.openwall.net (second.openwall.net [193.110.157.125]) by inbox.vuxu.org (Postfix) with SMTP id 6775520C56 for ; Fri, 4 Oct 2024 18:25:56 +0200 (CEST) Received: (qmail 7622 invoked by uid 550); 4 Oct 2024 16:25:51 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com x-ms-reactions: disallow Received: (qmail 7583 invoked from network); 4 Oct 2024 16:25:51 -0000 Date: Fri, 4 Oct 2024 12:25:42 -0400 From: Rich Felker To: musl@lists.openwall.com Message-ID: <20241004162542.GI10433@brightrain.aerifal.cx> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) Subject: [musl] Spin logic flaw in mutexes, etc. I realized while reviewing how we opportunistically spin trying to obtain locks that there's a problem with the logic: it was intended not to spin if there are already waiters (this is both a fairness consideration and a wasted-cycles one), but it can only see waiters that have already enterred the futex-wait phase. Waiters which are spinning are invisible. This leads to a situation where a large number of threads arriving at the same time hammering a lock will all spin. Just incrementing the waiter count before the spin is an obvious remedy, but by itself that would lead to the unlocking thread performing a useless and costly futex wake. I think we could redefine the waiter count to be adjusted by 1, so that a value of 1 would mean there's a spinning waiter, and N>1 would mean N-1 waiters potentially in futex wait that require a wake. With this approach, I think it would work to have the caller remember that it performed an additional waiters increment that needs to be reverted, or just do logic for transitioning 2->0 rather than 2->1. I thought this could be put in __wait, but I believe all the important callers actually use __timedwait which does not integrate the waiters increment/decrement logic. There might be other code paths that exit early where the waiter accounting needs to be reverted too though. For example I see one on line 80 of pthread_mutex_timedlock.c, but I think having this check is erroneous anyway, since the earier call to pthread_mutex_trylock would necessarily have caught this condition in the absence of state-corrupting UB. I'm not sure if we should try to avoid ever returning the waiters count to 0 between futex waits, which can happen now if there's only one waiter. Returning the count momentarily to zero allows a newly arriving waiter to spin (stealing the opportunity to take the lock). However stealing the lock is always possible before spinning anyway, anyway due to the trylock, and I don't think any complete mitigation for this is possible. The affected functions seem to be: - pthread_barrier_wait - pthread_mutex_timedwait - pthread_rwlock_timedrdlock - pthread_rwlock_timedwrlock - sem_timedwait and of course their callers. A similar issue applies to the internal __lock, but as it spins a lot fewer times and is called only in more controlled contexts, I'm not sure if it matters. The same mitigations can probably be applied to it if needed. Rich