From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 87019 invoked by alias); 1 Dec 2017 16:45:37 -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 86861 invoked by uid 89); 1 Dec 2017 16:45:27 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=3.2 required=5.0 tests=AWL,BAYES_20,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,FREEMAIL_REPLYTO_END_DIGIT,HTML_MESSAGE,KB_WAM_FROM_NAME_SINGLEWORD,RCVD_IN_DNSWL_NONE,SPF_PASS,T_RP_MATCHES_RCVD autolearn=no version=3.3.2 spammy=assets, H*UA:Win64, H*UA:x64, H*x:Win64 X-HELO: sonic304-22.consmr.mail.gq1.yahoo.com Received: from sonic304-22.consmr.mail.gq1.yahoo.com (HELO sonic304-22.consmr.mail.gq1.yahoo.com) (98.137.68.203) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 01 Dec 2017 16:45:23 +0000 Received: from sonic.gate.mail.ne1.yahoo.com by sonic304.consmr.mail.gq1.yahoo.com with HTTP; Fri, 1 Dec 2017 16:45:14 +0000 Date: Fri, 01 Dec 2017 16:45:00 -0000 From: "Xiaofeng Liu via cygwin" Reply-To: Xiaofeng Liu Reply-To: Xiaofeng Liu To: The Cygwin Mailing List Message-ID: <1543396632.5417641.1512146709346@mail.yahoo.com> Subject: mixed usage of lock protection and lock-free List template class in thread.h MIME-Version: 1.0 References: <1543396632.5417641.1512146709346.ref@mail.yahoo.com> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes X-SW-Source: 2017-12/txt/msg00005.txt.bz2 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#l110 =C2=A0110 template inline void=C2=A0111 List_insert (list= _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 /cygdrive/= c/Windows/SYSTEM32/ntdll.dll #1 0x000007fefd111430 in KERNELBASE!GetCurrentProcess () from /cygdrive/c/= Windows/system32/KERNELBASE.dll #2 0x0000000076fc06c0 in WaitForMultipleObjects () from /cygdrive/c/Window= s/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/cy= gwin1.dll #5 0x000000018013d0dd in pthread_cond::~pthread_cond() () from /usr/bin/cy= gwin1.dll #6 0x0000000180141196 in pthread_cond_destroy () from /usr/bin/cygwin1.dll #7 0x0000000180116d5b in _sigfe () from /usr/bin/cygwin1.dll #8 0x0000000100908e38 in std::_Sp_counted_ptr_inplace, std::allocator, void ()>, std::all= ocator, (__gnu_cxx::_Lock_policy)2>::_M_dispose() () The problem with the current implementation for concurrent insert and delet= e is explained at WikipediaNon-blocking linked list My question is how to solve this ? Adding lock protection in List_insert (r= emoving lock-freee) or implementing a complete lock-free List based on Harr= is's solution to use two CAS? Thanks. Xiaofeng Liu =20=20 |=20=20 |=20=20=20 |=20=20=20 | | | | | |=20=20 | |=20=20 Non-blocking linked list Several strategies for implementing non-blocking lists have been suggested= . | | | | =20 -- Problem reports: http://cygwin.com/problems.html FAQ: http://cygwin.com/faq/ Documentation: http://cygwin.com/docs.html Unsubscribe info: http://cygwin.com/ml/#unsubscribe-simple