DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id
	:list-unsubscribe:list-subscribe:list-archive:list-post
	:list-help:sender:date:from:to:subject:message-id:reply-to
	:references:mime-version:content-type:in-reply-to; q=dns; s=
	default; b=dBuItrIQQ04yOxAFttu+5MpHMfWDJqd+W3ldJE+sroEd6CIsJTzh9
	n4gANG/bAoGj06W5LzWUsRMc2Tmi7akP2Wd6yyK0I+wv9BwyNL7w/9lmJpD8qUG1
	T/tDuO/rAeOS1jNvo5WdK6aEMGn2G9NRylj6dGQCBBGq8kvBze2+qU=
Mailing-List: contact cygwin-help AT cygwin DOT com; run by ezmlm
Sender: cygwin-owner AT cygwin DOT com
Mail-Followup-To: cygwin AT cygwin DOT com
Date: Fri, 1 Dec 2017 18:15:36 +0100
From: Corinna Vinschen <corinna-cygwin AT cygwin DOT com>
To: cygwin AT cygwin DOT com
Subject: Re: mixed usage of lock protection and lock-free List template class in thread.h
Message-ID: <20171201171536.GA4325@calimero.vinschen.de>
Reply-To: cygwin AT cygwin DOT com
Mail-Followup-To: cygwin AT cygwin DOT com
References: <1543396632 DOT 5417641 DOT 1512146709346 DOT ref AT mail DOT yahoo DOT com> <1543396632 DOT 5417641 DOT 1512146709346 AT mail DOT yahoo DOT com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;	protocol="application/pgp-signature"; boundary="rwEMma7ioTxnRzrJ"
Content-Disposition: inline
In-Reply-To: <1543396632.5417641.1512146709346@mail.yahoo.com>
User-Agent: Mutt/1.9.1 (2017-09-22)

--rwEMma7ioTxnRzrJ
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Dec  1 16:45, Xiaofeng Liu via cygwin wrote:
> Lock protection and lock-free should never be mixed !=C2=A0
> =E2=80=8Bhttps://cygwin.com/git/gitweb.cgi?p=3Dnewlib-cygwin.git;a=3Dblob=
;f=3Dwinsup/cygwin/thread.h;hb=3D1f42dc2bcf58d3b8629eb13d53de3f69fc314b47#l=
110
>=20
> =C2=A0110 template <class list_node> inline void=C2=A0111 List_insert (li=
st_node *&head, list_node *node)=C2=A0112 {=C2=A0113=C2=A0 =C2=A0if (!node)=
=C2=A0114=C2=A0 =C2=A0 =C2=A0return;=C2=A0115=C2=A0 =C2=A0do=C2=A0116=C2=A0=
 =C2=A0 =C2=A0node->next =3D head;=C2=A0117=C2=A0 =C2=A0while (InterlockedC=
ompareExchangePointer ((PVOID volatile *) &head,=C2=A0118=C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0node, =
node->next) !=3D node->next);=C2=A0119 }=C2=A0120=C2=A0=C2=A0121 template <=
class list_node> inline void=C2=A0122 List_remove (fast_mutex &mx, list_nod=
e *&head, list_node *node)=C2=A0123 {=C2=A0124=C2=A0 =C2=A0if (!node)=C2=A0=
125=C2=A0 =C2=A0 =C2=A0return;=C2=A0126=C2=A0 =C2=A0mx.lock ();=C2=A0127=C2=
=A0 =C2=A0if (head)=C2=A0128=C2=A0 =C2=A0 =C2=A0{=C2=A0129=C2=A0 =C2=A0 =C2=
=A0 =C2=A0if (InterlockedCompareExchangePointer ((PVOID volatile *) &head,=
=C2=A0130=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 node->next, node) !=3D node)=C2=A0131=C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0{=C2=A0132=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0list_no=
de *cur =3D head;=C2=A0133=C2=A0=C2=A0134=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0while (cur->next && node !=3D cur->next)=C2=A0135=C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0cur =3D cur->next;=C2=A0136=C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0if (node =3D=3D cur->next)=C2=A0137=C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0cur->next =3D cur->next->next;=C2=A0138=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0}=C2=A0139=C2=A0 =C2=A0 =C2=A0}=C2=A0140=
=C2=A0 =C2=A0mx.unlock ();=C2=A0141 }
> The symptom I met is a job hang with the following stack:
> #0  0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects () from /cygdriv=
e/c/Windows/SYSTEM32/ntdll.dll
> #1  0x000007fefd111430 in KERNELBASE!GetCurrentProcess () from /cygdrive/=
c/Windows/system32/KERNELBASE.dll
> #2  0x0000000076fc06c0 in WaitForMultipleObjects () from /cygdrive/c/Wind=
ows/system32/kernel32.dll
> #3  0x00000001800458ac in cygwait(void*, _LARGE_INTEGER*, unsigned int) (=
) from /usr/bin/cygwin1.dll
> #4  0x000000018013d029 in pthread_cond::~pthread_cond() () from /usr/bin/=
cygwin1.dll
> #5  0x000000018013d0dd in pthread_cond::~pthread_cond() () from /usr/bin/=
cygwin1.dll
> #6  0x0000000180141196 in pthread_cond_destroy () from /usr/bin/cygwin1.d=
ll
> #7  0x0000000180116d5b in _sigfe () from /usr/bin/cygwin1.dll
> #8  0x0000000100908e38 in std::_Sp_counted_ptr_inplace<std::__future_base=
::_Task_state<std::function<void ()>, std::allocator<int>, void ()>, std::a=
llocator<int>, (__gnu_cxx::_Lock_policy)2>::_M_dispose() ()
> The problem with the current implementation for concurrent insert and del=
ete is explained at WikipediaNon-blocking linked list
>=20
> My question is how to solve this ? Adding lock protection in List_insert =
(removing lock-freee) or implementing a complete lock-free List based on Ha=
rris's solution to use two CAS?

First of all, please, please, please fix your MUA!  Just like your
mails to cygwin-patches a couple of weeks ago, your mails are pretty
much unreadable due to broken line wrapping.

Back to business: This code is working since 2003.  So, is that just
a theoretical problem, or a practical one?  If the latter, what is
broken exactly?

However, since you're asking, a lockless implementation where appropriate
is always welcome.


Thanks,
Corinna

--=20
Corinna Vinschen                  Please, send mails regarding Cygwin to
Cygwin Maintainer                 cygwin AT cygwin DOT com
Red Hat

--rwEMma7ioTxnRzrJ
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIcBAEBCAAGBQJaIY43AAoJEPU2Bp2uRE+gWtEP/jK1KkuHBuUAIXz8SSy5W1aq
bxqxdUVflw53ztkAX80+g38UM+d0Lfun/FCQMpbZLdJvWTZVFDEwgZ8eAOT0ftoH
iNTLgtPP/0gOnDxTIFfRq0LOkovRY1NhNRfVpx9diCRCrDiQldI+FLuy8uowOG78
EJutkKv4kHm6YuKs+TpQmav/wFBS5MrBOqn9IgpImGREhavwcGs3R0OkvbtMXfvA
UPfwwE5MmFLGCwnGtxacnig+9s/IdgRBoGPFY4C/2EqIVpKbPHJj6nNuLv3TSiFG
OK8paQkT1HVi3malqkFsk+xOIxLaaECi/tDIzy+SuozlJwCGe3+IsaAS5nS0mHpE
vmYVAufMvzzLjEueM+tgc2FmgyN/5CkwpbvjjZ4r/Zq5W5RZH/pm6BBJ6dbpWAnj
ktLWPtVBoRBZXBQrKcKWkvPprQUcOvb3owNx9tNfYBvLNymjsMbP85z0lb2kndKR
i4gRLIBhE3N0lMAWtO3zfgOkm08tKkuAQyxaZ6IefI2cUyjHmmy1RRXYbAHn7aOk
p2FE9dtK9gBlI25xNzrJznWpKJbkYF1VR8A7s8H01LhCDHYL79YQ5Qkd08f/0Eu2
iAjPuXWTs0Pd8eq5bH2FtdgPcj2G3OO0OfZPwVsVM8wnU3BJ+upy7W8HmbsS4kh5
Ax2TbBmgtyumxFu9qEDH
=HLVn
-----END PGP SIGNATURE-----

--rwEMma7ioTxnRzrJ--