From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11534 Path: news.gmane.org!.POSTED!not-for-mail From: Jens Gustedt Newsgroups: gmane.linux.lib.musl.general Subject: Re: [PATCH] (V2) a new lock algorithm with lock value and CS counts in the same atomic int Date: Tue, 20 Jun 2017 17:36:29 +0200 Organization: inria.fr Message-ID: <20170620173629.4b177585@inria.fr> References: <868874$8aqkr1@mail2-relais-roc.national.inria.fr> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; boundary="Sig_/=D5EGZPC2hy=K0bu4Cb5x6o"; protocol="application/pgp-signature" X-Trace: blaine.gmane.org 1497973021 19855 195.159.176.226 (20 Jun 2017 15:37:01 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 20 Jun 2017 15:37:01 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-11547-gllmg-musl=m.gmane.org@lists.openwall.com Tue Jun 20 17:36:57 2017 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by blaine.gmane.org with smtp (Exim 4.84_2) (envelope-from ) id 1dNLD5-0004tD-HI for gllmg-musl@m.gmane.org; Tue, 20 Jun 2017 17:36:55 +0200 Original-Received: (qmail 13715 invoked by uid 550); 20 Jun 2017 15:36:43 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Original-Received: (qmail 13648 invoked from network); 20 Jun 2017 15:36:41 -0000 X-IronPort-AV: E=Sophos;i="5.39,364,1493676000"; d="scan'208";a="279847557" In-Reply-To: X-Mailer: Claws Mail 3.14.1 (GTK+ 2.24.31; x86_64-pc-linux-gnu) X-Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwBAMAAAClLOS0AAAAAXNSR0IArs4c6QAAACRQTFRFERslNjAsLTE9Ok9wUk9TaUs8iWhSrYZkj42Rz6aD3sGZ Xref: news.gmane.org gmane.linux.lib.musl.general:11534 Archived-At: --Sig_/=D5EGZPC2hy=K0bu4Cb5x6o Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: quoted-printable Hello Alexander, On Tue, 20 Jun 2017 17:41:35 +0300 (MSK) Alexander Monakov wrote: > > + /* We can only go into wait, if we know that > > somebody holds the > > + lock and will eventually wake us up, again. */ > > + if (current < 0) { > > + __futexwait(l, current, 1); =20 >=20 > Here you reuse the value of 'current' after resuming after a > futex-wait. But if the lock is under contention, with high > probability other threads have modified the lock while we were > sleeping, so the value of 'current' is likely stale, and the > following a_cas is pretty much guaranteed to fail. Wouldn't it be > better to reload current =3D *l after resuming? Not to my experience. The benchs that you can find in the references that I have given, clearly show that this strategy is better than the current lock strategy (and a lot of variants that I tried.) These benchmarks were performed on two architectures that are representative, I think: x86 for one that locks the bus and arm for one that uses a monitor. (And the gain on arm is more important.) For all what I found, the real cost here is the bus transfer (caches are probably not uptodate, anyhow) so doing a CAS compared to a load is not much more expensive. On the other hand, if we guess "current" correctly, we are done. Also this guess is not as bad as it might appear. Comming out of the wait should usually be after a wakeup, were just the current lock holder left the CS. So the educated guess in that situation, that the lock is free and there is one thread less in the CS, works quite well. And if it doesn't, and all other threads of the CS are in kernel sleep, the next iteration does the trick. So for the usual case you'd deal one forced load plus one CAS, against a single CAS in the good case, and two CAS in the bad one. After coming back from a kernel sleep, you have other things to worry (reloading all your data, e.g). Again, I'd like to emphasize that the performance of this part is not very important. I wouldn't know a program could hammer as much on a lock that uses this code inside musl, such that a lot of threads are stuck in that congestion loop. Thanks Jens --=20 :: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS ::: :: ::::::::::::::: office Strasbourg : +33 368854536 :: :: :::::::::::::::::::::: gsm France : +33 651400183 :: :: ::::::::::::::: gsm international : +49 15737185122 :: :: http://icube-icps.unistra.fr/index.php/Jens_Gustedt :: --Sig_/=D5EGZPC2hy=K0bu4Cb5x6o Content-Type: application/pgp-signature Content-Description: Digitale Signatur von OpenPGP -----BEGIN PGP SIGNATURE----- iF0EARECAB0WIQSN9stI2OFN1pLljN0P0+hp2tU34gUCWUlA/QAKCRAP0+hp2tU3 4m3rAJ9GqABI7tvL9u5Nt5kODaXW0G2F9QCfXsySbn1yO85OXiG51OngF+yIRN4= =7OC9 -----END PGP SIGNATURE----- --Sig_/=D5EGZPC2hy=K0bu4Cb5x6o--