From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-1.0 required=5.0 tests=MAILING_LIST_MULTI, RCVD_IN_MSPIKE_H2 autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 29330 invoked from network); 22 Feb 2023 18:12:35 -0000 Received: from second.openwall.net (193.110.157.125) by inbox.vuxu.org with ESMTPUTF8; 22 Feb 2023 18:12:35 -0000 Received: (qmail 7194 invoked by uid 550); 22 Feb 2023 18:12:31 -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 Received: (qmail 6123 invoked from network); 22 Feb 2023 18:12:30 -0000 Date: Wed, 22 Feb 2023 13:12:17 -0500 From: Rich Felker To: Alexey Izbyshev Cc: musl@lists.openwall.com Message-ID: <20230222181217.GD4163@brightrain.aerifal.cx> References: <20221122000958.GQ29905@brightrain.aerifal.cx> <87064ce2eef96ffbced93da7812d5358@ispras.ru> <20221214014857.GA15716@brightrain.aerifal.cx> <583865e860854d059f50d23a9acd7a8f@ispras.ru> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <583865e860854d059f50d23a9acd7a8f@ispras.ru> User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [musl] sem_post() can miss waiters On Wed, Dec 14, 2022 at 01:29:54PM +0300, Alexey Izbyshev wrote: > On 2022-12-14 04:48, Rich Felker wrote: > >On Tue, Nov 22, 2022 at 08:41:44AM +0300, Alexey Izbyshev wrote: > >>On 2022-11-22 03:09, Rich Felker wrote: > >>>If I understand correctly, the cost of the first option is generally > >>>an extra "last" broadcast wake that shouldn't be needed. Is that > >>>right? > >>> > >>>For example, if sem starts with count 0 and thread A calls wait, then > >>>thread B calls post twice, both posts make a syscall even though only > >>>the first one should have. > >>> > >>Yes, exactly. > >> > >>>What if you instead perform the broadcast wake when the observed > >>>waiters count is <=1 rather than ==0? This should have no cost in the > >>>common case, but in the race case, I think it forces any hiding > >>>(just-arrived) extra waiters to wake, fail, and re-publish their > >>>waiting status to the waiters bit. > >>> > >>Indeed, I think this solves the overhead issue quite nicely, thanks. > >>So sem_post wake up logic would basically boil down to this: > >> > >>* WAITERS_BIT is set and waiters > 1: don't reset WAITERS_BIT since > >>it's likely that some waiters will remain (and it's always fine to > >>err on the side of preserving the WAITERS_BIT); wake a single > >>waiter. > >> > >>* WAITERS_BIT is set and waiters <= 1: reset WAITERS_BIT and wake > >>all waiters. In non-racy cases only a single waiter will be woken. > >> > >>* WAITERS_BIT is unset: don't wake anybody. Even if there are some > >>waiters, another sem_post (that reset the WAITERS_BIT) is > >>responsible for waking them. > >> > >>In code: > >> > >>int val, new, waiters, priv = sem->__val[2]; > >>do { > >> val = sem->__val[0]; > >> waiters = sem->__val[1]; > >> if ((val & SEM_VALUE_MAX) == SEM_VALUE_MAX) { > >> errno = EOVERFLOW; > >> return -1; > >> } > >> new = val + 1; > >> if (waiters <= 1) > >> new &= ~0x80000000; > >>} while (a_cas(sem->__val, val, new) != val); > >>if (val<0) __wake(sem->__val, waiters <= 1 ? -1 : 1, priv); > > > >Yes, this looks good to me. How is the attached patch? > > > The patch looks good to me. Just a heads-up: this patch is in my big queue of stuff to push, and should be upstream soon now. Rich