From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/5798 Path: news.gmane.org!not-for-mail From: Jens Gustedt Newsgroups: gmane.linux.lib.musl.general Subject: Re: Explaining cond var destroy [Re: [musl] C threads, v3.0] Date: Sat, 09 Aug 2014 08:47:34 +0200 Message-ID: <1407566854.4988.231.camel@eris.loria.fr> References: <1407358510.24324.328.camel@eris.loria.fr> <20140806220453.GD1674@brightrain.aerifal.cx> <1407365015.24324.334.camel@eris.loria.fr> <20140806231539.GE1674@brightrain.aerifal.cx> <1407397851.24324.354.camel@eris.loria.fr> <20140807161342.GH1674@brightrain.aerifal.cx> <1407430024.24324.387.camel@eris.loria.fr> <20140807172514.GI1674@brightrain.aerifal.cx> <1407489627.24324.419.camel@eris.loria.fr> <20140808191405.GP1674@brightrain.aerifal.cx> <20140808204855.GQ1674@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/signed; micalg="pgp-sha1"; protocol="application/pgp-signature"; boundary="=-pRU165iyEMjUSuGwuWyq" X-Trace: ger.gmane.org 1407566877 31739 80.91.229.3 (9 Aug 2014 06:47:57 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 9 Aug 2014 06:47:57 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-5803-gllmg-musl=m.gmane.org@lists.openwall.com Sat Aug 09 08:47:52 2014 Return-path: Envelope-to: gllmg-musl@plane.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1XG0RU-0007Oa-Ha for gllmg-musl@plane.gmane.org; Sat, 09 Aug 2014 08:47:52 +0200 Original-Received: (qmail 24252 invoked by uid 550); 9 Aug 2014 06:47:52 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 24244 invoked from network); 9 Aug 2014 06:47:51 -0000 X-IronPort-AV: E=Sophos;i="5.01,831,1400018400"; d="scan'";a="88790836" In-Reply-To: <20140808204855.GQ1674@brightrain.aerifal.cx> Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwCAYAAABXAvmHAAAABHNCSVQICAgIfAhkiAAAEb9JREFUaN7VmXuQ3lV5xz/n/O7v7333fffdW3azSTY3Qi6wGy4aEc0qWlGhWcAq7WiDrWNpO61paS29EpzWaevYpvfL2JK0VRBbBxQtg0U2BRGKhIAI4ZKwSTbZ+3u//G7nnP7BtGM7UyVAnfb56/xznuf7nXnOnOf5fuH/eYjXI8mDn/5k8ch90xNj+eKka8xkI1MTGmY6Rk/XpD5w091fPvnf7xz8sQ/sLTQ6k54SY2mW1mQY3DVX8Kdv/PvPnfyBE7hn797bxBPP3NBv28RAqgyzJqNgJIs5q7bhHW+94Yd+5/fuBrjj5l/cs/LUs/vNiVMTo5aNJQX9lks3iaivHqlt/9D7xs778Y/Uf6AE/uWa6x7wT52ZTDyLKEkoOHmW4oSaSDFxQmq7tHPuDJ5TUkv10iAGgSLvediZotf16HS6KG1RuXDT/g99/vO3vtLa8vUgELuCVAja0mVJKRaylGbgYnwP27bImYRcozkmKrWS53vYjosfhNSUIjXQUoq2K0ksRdZqTZ5Lbfs/Dl/66E/uSebmb8hF8URab48JS+IPDVJtto9uuHj8wKW//6lD/1OSznxtLEPRv2kdPH2MSBpkqlDGkLoOIgGkIWcEiTYsk1JSDpGUFAAcBzfRCKXxV+ql7/XWnn7uxcm3vOGS2rrR1UcLV+6pC4B//tjPjGdHjhwttFOEcMmMAgFeLkezWsOTkmigfyYZGTzYN7HtwFt u+rU6wJnprxQf/JvP7beffH5fBIwGIZqEutJUlCKSNoFjYbQiihOkFmih0FJgSUGIpGxstE6RwiLQmsyzcXZesO8N1773YOHKPfUv/uxP726ePjsVNVoT9WZjMq02kRpEKay9+UPXjQmAL1991UuDZ+fGQulSVQrpuqg4pWkkupSjVGshtGZJpzQ9DysfQqZIkgzR7 jAc+qAFrm2xTIRJJKnr0okTfCnQKLRlo9MUicGWL7dcnCnytoOTKTxpERpBv8moomm7AZFjEddb9EiHdhJhPJdYanQKUZrivmH7Pnlm+itFuVgdi7WkpSSJdFlqRwRugLAkQakXJQ06cAhcB0tnRI0mstOllKYEvk8qJJGj8IygID16hwZBGIzIsIXCRREq6DGSsu9RkBYBBldKbCFwbMnA2mH8wKIrbQrGY1WkKbQ6DFkWOQEicMks8JTEQRJI0LOLJbvxwosTMlMk0kYbjTCGci4gzrr0Sod0YQFHWiSuRTHMkbRaCCxMZlh2FLGQLEjBmHFIhUBrEI0OlgYnyNN0LFKliYxGeT69rouqtOjP5+lLEtxugosgOjNHj7ZRGmwjaDoGX9skKEQQIFptkAIjIWckCQIrE9ija8aOznk5wiwh9lw8aeMlMamUeEKis4wOFiaFRtpEYxBJSoQA4ZM4ksgSPG4E9Siibjt02xUaUQsnzFFfSZlPM4TRlPp7yQWCs/PzlMs53HrMRLGPt/f2UFYRbkOzbGm6JkPgYjAgbVo6I/Ntup0unuPgWAK0RaLVy//AfVe864lgcWkicz1yloNvoJMmpFLTsiCJNIFt0VERHdcnGyxPW5598BmlJo6tVPc9v1RB2CHdqMWOYpkLCwHnhyHVTHNcpTxUrVCp1rAtyYZ1w0i3SLFk89A3/g2UZH3O4ubL30RxsU5ldhkpDFJIbGFRE4rYSLQQRHGEJQQeFm7gYHaev98CuO6NF62q1hqTKktJlKarNW0JDZUgHA9dys/Y q4emnQ3Df3nxj7z7+t2f+pO/Ysv5U0dm525uKYty3wCetPjRdYNcjaaQabq1Oq1MkVOKkc1reGFhiWIuj7C6JGlKyZNsNor3n7eFStLlkcoKz61fvX/79u3T9cWliTBWvrQEHa0QQmIZgdIK27FQmaKVxIRbN+77z5/4sT/+1PjJEycmosWVmXJvP3YpZM3aNYyuWz dTuHLPf5lPrnr3VXtPnDp10HNDlIqROEwO9fG+VosXspQ7lyto3+fE8ln2rlpDfniQP332WRCCd75tB43jZ7jUDRlspTiugxAeR+I2960s0hBy3503fmT69FcfONian5uQliDIF+m2YyKlUUIRxRF968eOfuC+r+4851Hill//+PiRx79ztNrs0mm0KZaLZEnGWwsB725WOFRv8HAmSDodSo7D3oF+bMfirxbOYkKHQDhc5lusznxaaO6fO8O2fIE9vf1M0+Go0jM73nT55EcvGa8duedr+3S1si8v7VLnzDxRpkjCHGJ4aHr1utVT7/mzP6/b5wJ++v57izf9wi8dVNrHcT3yxQK27RJ3Y6zM0LI1b+0ZoFldIvFsxvsH6LMELQOpkST1GBVq3NIAvvC54ztPcTwRLOs2b+sf4u2RS5JFY1++5yt3XbXnvZPX3/n5W4FbH/nLA+ueuOeBG/zefG3ynW87+N3D3jkRuP3226fiVEwkOiV0bNIsJep28QOfqOAjl2DEElw1WCZKFGUtkK6h7fj4DpRKfURJjeGwSE/UJcJga4d6p0lHCoo64w1BkfsqtYnf/LVPHgSuAdh1476TwMsD3t9/9jUMc9pMSiGxJRgV0+22Wa7XqTfqHH7pON8u9/NE6BB5PnZPD42BkMe14IG4gVXIsVSvkijFU2fPIrOUraPrsD3Jlt4SnTQlsi2qtqLSarG0VJnaObHztu8HyTqX9vn6Aw/cMTw0TJpkeH6AhaIncCn3FkmFzWNzc3y7U+ObjTqPVJs8Vq1h1oScabdoV xWxyQg9l57BATZZDpuCgH5PMrVxM3G3g513WfNDW3liYRGsPN1ua2LHtq0zM6dOPfmqCDx15227/+ILd58EaNa717/00smp3bsvo7fcS3VpGTcAKV2q1QZJ3MVIC88JsFJN2c+xbrDM+aHPlqE+ji0vY7kWvaFhaaXJzs3nYaoNNq/tJ1/tsiwtnpEOtz/+HHNLMXG UkmYp7XarVKlWD53TQtO89+7iN//stoPWqdkpPx/Wur3F6WccZ+KFdnuskXNZaCVkiWJ++Qy+59EbuHi6y1t2XkL27Ak2CJssS6lHMYPCYDLDP/dJvj1fQ0qb+WoMqk3BzrFlYAidc5hZXAQnh9DQ6TbRQhF3U7Is4eZf+YWJj9308Se/5z7w3fH8s8fGnNOnp1ZJie52S+VOd2oIeJObo2Vs5i2JWZWn1e/TrjQZK/WSiyPCE2eImh1S12PJaEJtYbsCN81oL7eROPQVodVI6ZiA1MvxQhyhOxGWlcOkKUHg4aQOaaoQ0hDFXf7pi3dPAk+e00r56HuurubnzpZsY5NKiYMhwUagcY1CCINB0pACIQXLoaBHWdTbXbTwWHEhHwQE9SbVgRJ/Mz/Hi4sr7H3fOIuVJvc+OEsYFnG8AKETGs0WljBYtk2j3nkZmRDoqMPqdSNHHztyZOc5rZTpQHlfIh2MpdDSgAZbZ/hGgzRIaSEF9AiNLyWylRFbNh0bfKEZsCxkK2JxZJi/Pv0CJyornLd5DQ8++hxHv7NIEFg0W00ajRqNRh3XtciUot5okBlFZgzSssm04fjxExN/+kcHxs+JwOWHDh06u3bkQNV1a7ZSIDWehEQoUgEaQGtMlpHlLXp6XPLdjFyqwBMsAvfR5D4Z0fFKbNqwgWajgnQHWF6K8V0H35EIrQFodWKSzGAJQc63sS2JylKkZaO1ZnTNqplXpUo07727+NV/vPuAv3D2hrWpRtYaZJbEwmBlINf00144S35kgMZsxEpgc0zEfL3Spu 1LklihlU2u6NBtNZDaohXHIDKadYWRLsZkZFhgNCaLcB2XzECWalAZhR6v9vzx472v+BF/dxSu3FPf9cY3z0TNLgO+YFNfHzozJHFE4CvW1CPGBvtYabQ5YQuON+aI7YCqUTSX2hgTUeop025IstSiv1wiUQu4fkiz2SBTHaSQ9AQOaZqBk6MTdzFGYAnB0FAvWjD9 fVWJ7xUjI+XJ54/NMNeVLM3XMEZjWRYGzf2dWUp5kJZNmlmE+RDdaXHpznFOzc6xOL8AKIqlArVaTKdTQSvD4sIifb29KOOgshaOJal0UzSgjcQYyNKU4zMzXHTR+F2vSRdKOm3CnIvnO4QFn77ePL7vErVaqLhN4OUYcGHL+j7iVoeBoX5mT5+mtjzHeRtLDA2UWFqYx3c8Ot2MocE875y8iMCHLElIogytDVJKjFIYLUiiCKVihkeGD379Xx869JoICGHj2C4qU2ASFqsLNFptvMBj9ZoSlzgen7hiFz919QQDoWB+9gwqU4SFXk6eXGHN6kH6e21Wls7SX3Zot5t889HvUKlFL8ssJkOgAIXv2+gswqiYjRvHjv7qr+zb94qEre8Vnu/juRlKCTJlgQhBxdRaTVb1lNh7yRb41tOUR99G72Afza6h0e7gezZWOMzRY7NIZVHoyVOtxli2hSUEaarJlwLqOqOTaoTMYVmagXKOQnHk6O/+7u9MTl5xZf01D3NrR0dK7W58pe/naHS7SB1z7fg6fm58I2/OuRSencH2HIIffjNzLRhfv5ZGo85itU6aSRr1Jq6laEcJjcgwWA7YMOoS5B2WKx38oEAUJURRhko1nm9P/8EffvrK7wf+FbfQjT/zUwdzoTvTjVv4UlK0XHZs3UTZd1mbaqyiCwKc02d4v51ycW2Zy9Zvw+AQ5DxW9RcoFwRDZZ9VA2UAdu26iD3vupQLto5SrXSwpIPjKsbWr+aDH/zg/lcC/pzU6Y98eO/4iReem67WOyU/6KFdX2S kELLRU3y0d5Cg1aEZBqSxQJdtprXL5546guXm6QtCwmKOTrvC2NoSq8tw8fYSDx9t8tATVSqNOo16lzdech7Ndrz/a4e/9fqr05+57dCTW7edtz/fE2JIySyHlxqKr8+3OFXooykND8ocf1vwuD1WHO1G5AKPUi5EYVGpLeA4OcqhZtVASKtjkLZFpjM6nZjNG0dnN p63fepcwL8qf+BdV+x+YGmxNimRtNOUJI3Z1APX7NjBPxx5ntjLQRLTTBKGSz4jwz3UajWGhgap1uqcPFXh0ovX88zTz1Mo9tJNQdiF6d273zh1y29/un6ueM7ZH7hw24apfGDPJN02ri0phXlUaZi/e3qGSpziOgKjI8qhS73eQKuUIBAsLS3i+x5DQ0W6zRUyY1hpiNrAwND+PXve+6rAv2qH5rdv+dXxr933tbtWlqpj/cOjkAkWaosUHUW5UGBmYZF1AwM0WjUKvX2g25TLJZ56dh7Pztg5vmFm8vIL9udHLrtr6trrXxXw12wxTd9/b/ETt95y15lTC5Pbtu2gUVkgaTeItSJKDI4Fo6t66cZtbNuiUu8QlvpnVq0auuGzd3758P8Jl3L6/nuLf3Tg05OWEJOFfH4iiuLJOMlYXmnSrDURaIxJEFJzwYXb9x+640u38v8hPvazP717+5atZtvmrWbN6vVm9dBqc83VP7znf6OW/Xok+a2b941XG9HY7KmTE81me/Khww+P5XMFkszQiFIKPQEQTwF3/58zui+98IK9KA4W8gVOn10kF4Tk8z7SdWl2I6JWA0fE9A+VqdXq0x/+iQ/f8PM3/cbJ14vAa7JZr3rXFR+bn188aFk2veUCxXIPQeiDkdQbbXKuZP3qIju3rcVKm7z9su2TTxy+a+Yzn3z/La8XAevVXrzu2j3jBnlXrVonVSmtbpdms40AwlyeTGeEtk2r00HYLhdsXc/OrR4XbVaU/Mbkb930nqme0rrowUefffIHTuC6a/fsPfbM C3d0WolfKhTp6clRyhcg04xtGCHt1Dh/rExRamYWGyxXa7xn1yYuvkAwP7fClg0Zhx+qr/rM7d+Yesc73nHD5OW7Zh478tRzPxACH/iRa245duzkAdsJfMuy8aXm/FUFlpeWWOm2WZidI9WapaUlFIaTlQ4jfR6/vO9D2NE32LTeYnZOUmnA6PAohx9+qnTy1NnrP/ Cj15cu23XZI4/826Px/xqB37z547sPH374oOvnKTsOb+1zuCoImZARM8ZiLlKkXcWOcoFRJ+Do/CwFO4e2DEe+9Ti+ZXA8ny/cU+X4bMKRZxZIVEiqXI6/+NKuUzPHb7z40ovnX3zx+Ctuq38HyuqWG7Tu+A0AAAAASUVORK5CYII= X-Mailer: Evolution 3.4.4-3 Xref: news.gmane.org gmane.linux.lib.musl.general:5798 Archived-At: --=-pRU165iyEMjUSuGwuWyq Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: quoted-printable Hello, Am Freitag, den 08.08.2014, 16:48 -0400 schrieb Rich Felker: > On Fri, Aug 08, 2014 at 03:14:06PM -0400, Rich Felker wrote: > > I think I may have a solution you'll like: > >=20 > > We can perform the release of the lock via a compare-and-swap rather > > than a simple swap. In this way, we can know before releasing the lock > > whether it's going to require a wake or not: > >=20 > > - If waiters was zero and the cas from owned/uncontended to zero > > succeeds, no futex wake operation is needed. > >=20 > > - If waiters was nonzero, or if the cas fails (thereby instead > > requiring a cas from owned/contended to zero), we can do the > > following: > >=20 > > Don't use a userspace CAS to release; this would allow the lock to be > > acquired by another thread, released, destroyed, and freed before the > > futex wake is performed. Instead, use FUTEX_WAKE_OP to atomically > > perform the atomic assignment and futex wake. >=20 > FUTEX_WAKE_OP is highly under-documented, and i'm worried it might be > unsupported on some archs (since the atomics for it have to be > implemented on a per-arch basis in the kernel) but of course we can > just fallback on archs where it's not supported yet. >=20 > Anyway, the behavior seems to be: >=20 > - Futex acquisition for uaddr1 and uaddr2 both happen prior to the > atomic operation, and this hold locks that seem to prevent new > waiters on the futex(es). This should preclude any risk of waking a > new waiter that arrives after the atomic operation, as desired. >=20 > - Both uaddr1 and uaddr2 are hashed, with no check for equality. This > is a fairly costly wasteful operation, but could be fixed on the > kernel side. At present I suspect they don't care because > FUTEX_WAKE_OP is considered unnecessary, but if I raise it on the > glibc bug tracker thread for issue 13690 as a solution to the > problem, I think there would be a lot more interest in optimizing > this kernel path. >=20 > - After the atomic operation is performed, a wake is always performed > on uaddr1 (based on the previous acquisition); this fact is omitted > from all the documentation, but it's obviously intentional since > otherwise the uaddr1 argument would not be used for anything but > wasting time. The wake on uaddr2 is conditional on a comparison. >=20 > - No allocation is required anywhere in the operation, so we don't > have to worry about lost actions on OOM. For plain FUTEX_WAKE this > would not have been an issue (if acquirin the futex required memory, > then failure for FUTEX_WAKE to acquire it would mean there was no > FUTEX_WAIT taking place anyway), but for FUTEX_WAKE_OP, failure > would omit the atomic operation, which must take place even if there > are no current FUTEX_WAIT waiters (e.g. if the FUTEX_WAIT was > interrupted by a signal handler). >=20 > Based on the above, I think it's safe to move forward with using > FUTEX_WAKE_OP. It seems optimal to me to use uaddr1=3D=3Duaddr2 and a > comparison that always yields false, so that the wake only goes to > uaddr1. This will allow the kernel to optimize out double-hashing in > the future by checking for uaddr1=3D=3Duaddr2, and already optimizes out > the double-iteration of the hash bucket for waking purposes. >=20 > Any further thoughts on the matter? I think we should finish the > private futex support task before starting on this, so that we don't > do new work that's going to conflict with a pending patch. This looks promissing, but I yet don't know enough about these less common futex operations to comment more on it. Generally I think that the control structures should be as tight as possible, give provable properties in the mathematical sense. The interaction between user- and kernelland should be minimal, and we shouldn't provoque reactions of the kernel that concern threads (or even process) that are not really targetted.=20 Jens PS: I will be a bit less available in the next days. --=20 :: INRIA Nancy Grand Est ::: AlGorille ::: ICube/ICPS ::: :: ::::::::::::::: office Strasbourg : +33 368854536 :: :: :::::::::::::::::::::: gsm France : +33 651400183 :: :: ::::::::::::::: gsm international : +49 15737185122 :: :: http://icube-icps.unistra.fr/index.php/Jens_Gustedt :: --=-pRU165iyEMjUSuGwuWyq Content-Type: application/pgp-signature; name="signature.asc" Content-Description: This is a digitally signed message part Content-Transfer-Encoding: 7bit -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iEYEABECAAYFAlPlxAYACgkQD9PoadrVN+KxMQCeNzLO3Yb34adpdY2HDeLeWBeU hy0An3IR0fOo0fZg88DZLP4UkjRzUaA8 =qc/p -----END PGP SIGNATURE----- --=-pRU165iyEMjUSuGwuWyq--