From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 36494 invoked by alias); 1 Dec 2017 17:15:42 -0000 Mailing-List: contact cygwin-help@cygwin.com; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: cygwin-owner@cygwin.com Mail-Followup-To: cygwin@cygwin.com Received: (qmail 36484 invoked by uid 89); 1 Dec 2017 17:15:42 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-101.4 required=5.0 tests=BAYES_00,GOOD_FROM_CORINNA_CYGWIN,KAM_LAZY_DOMAIN_SECURITY,KB_WAM_FROM_NAME_SINGLEWORD,RCVD_IN_DNSWL_LOW,SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=cygwin-patches, cygwinpatches, xiaofeng, business X-HELO: drew.franken.de Received: from mail-n.franken.de (HELO drew.franken.de) (193.175.24.27) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 01 Dec 2017 17:15:40 +0000 Received: from aqua.hirmke.de (aquarius.franken.de [193.175.24.89]) (Authenticated sender: aquarius) by mail-n.franken.de (Postfix) with ESMTPSA id 2355D721E281C for ; Fri, 1 Dec 2017 18:15:37 +0100 (CET) Received: from calimero.vinschen.de (calimero.vinschen.de [192.168.129.6]) by aqua.hirmke.de (Postfix) with ESMTP id BE9BB5E01A4 for ; Fri, 1 Dec 2017 18:15:33 +0100 (CET) Received: by calimero.vinschen.de (Postfix, from userid 500) id 30747A81808; Fri, 1 Dec 2017 18:15:36 +0100 (CET) Date: Fri, 01 Dec 2017 17:15:00 -0000 From: Corinna Vinschen To: cygwin@cygwin.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@cygwin.com Mail-Followup-To: cygwin@cygwin.com References: <1543396632.5417641.1512146709346.ref@mail.yahoo.com> <1543396632.5417641.1512146709346@mail.yahoo.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) X-SW-Source: 2017-12/txt/msg00009.txt.bz2 --rwEMma7ioTxnRzrJ Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-length: 4010 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 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::allocator, void ()>, std::a= llocator, (__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" Content-length: 819 -----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--