From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 109087 invoked by alias); 16 Feb 2018 16:25:08 -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 108929 invoked by uid 89); 16 Feb 2018 16:25:07 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-6.7 required=5.0 tests=AWL,BAYES_00,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,FREEMAIL_REPLYTO_END_DIGIT,GIT_PATCH_2,RCVD_IN_DNSWL_NONE,SPF_PASS,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=H*UA:YahooMailBasic, H*x:YahooMailBasic, H*x:Win64, H*x:x64 X-HELO: sonic314-19.consmr.mail.gq1.yahoo.com Received: from sonic314-19.consmr.mail.gq1.yahoo.com (HELO sonic314-19.consmr.mail.gq1.yahoo.com) (98.137.69.82) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 16 Feb 2018 16:25:04 +0000 Received: from sonic.gate.mail.ne1.yahoo.com by sonic314.consmr.mail.gq1.yahoo.com with HTTP; Fri, 16 Feb 2018 16:25:03 +0000 Date: Fri, 16 Feb 2018 16:25:00 -0000 From: "Xiaofeng Liu via cygwin" Reply-To: Xiaofeng Liu Reply-To: Xiaofeng Liu To: Message-ID: <451353526.1938418.1518798301806@mail.yahoo.com> Subject: Re: mixed usage of lock protection and lock-free List template class in thread.h MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable References: <451353526.1938418.1518798301806.ref@mail.yahoo.com> X-SW-Source: 2018-02/txt/msg00183.txt.bz2 Here is more detailed information to demo the infinite loop due to corrupti= on of the list, using one "-g" compiled cygwin1.dll in my cygwin: After the job hang, the stacks are: (gdb) info thread=20 Id Target Id Frame=20 * 11 Thread 15220.0x1ef0 0x000000007711afb1 in ntdll!DbgBreakPoint () from = /cygdrive/c/Windows/SYSTEM32/ntdll.dll=20 10 Thread 15220.0x1274 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects= () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll=20 9 Thread 15220.0x28c4 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects = () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll=20 8 Thread 15220.0x3f1c 0x000000018021b9e6 in void List_remove= (fast_mutex&, pthread_mutex*&, pthread_mutex*) () from /usr/bin/cygwin1.dll= =20 7 Thread 15220.0x20a8 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects = () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll=20 6 Thread 15220.0x1980 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects = () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll=20 5 Thread 15220.0x389c 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects = () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll=20 4 Thread 15220.0x3c1c 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects = () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll=20 3 Thread 15220.0x3290 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects = () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll=20 2 Thread 15220.0x3db0 0x000000007711bd9a in ntdll!ZwReadFile () from /cygdr= ive/c/Windows/SYSTEM32/ntdll.dll=20 1 Thread 15220.0xf6c 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects (= ) from /cygdrive/c/Windows/SYSTEM32/ntdll.dll=20 (gdb) thread 8=20 [Switching to thread 8 (Thread 15220.0x3f1c)]=20 #0 0x000000018021b9e6 in void List_remove(fast_mutex&, pthre= ad_mutex*&, pthread_mutex*) () from /usr/bin/cygwin1.dll=20 (gdb) x/10i $pc=20 =3D> 0x18021b9e6 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+150= >: mov -0x8(%rbp),%rax=20 0x18021b9ea <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+154>: mo= v 0x10(%rax),%rax=20 0x18021b9ee <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+158>: mo= v %rax,-0x8(%rbp)=20 0x18021b9f2 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+162>: jm= p 0x18021b9cb <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+123>=20 0x18021b9f4 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+164>: mo= v -0x8(%rbp),%rax=20 0x18021b9f8 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+168>: mo= v 0x10(%rax),%rax=20 0x18021b9fc <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+172>: cm= p 0x20(%rbp),%rax=20 0x18021ba00 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+176>: jn= e 0x18021ba16 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+198>=20 0x18021ba02 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+178>: mo= v -0x8(%rbp),%rax=20 0x18021ba06 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+182>: mo= v 0x10(%rax),%rax=20 (gdb) x/10i $pc-150+123=20 0x18021b9cb <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+123>: mo= v -0x8(%rbp),%rax=20 0x18021b9cf <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+127>: mo= v 0x10(%rax),%rax=20 0x18021b9d3 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+131>: te= st %rax,%rax=20 0x18021b9d6 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+134>: je= 0x18021b9f4 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+164>=20 0x18021b9d8 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+136>: mo= v -0x8(%rbp),%rax=20 0x18021b9dc <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+140>: mo= v 0x10(%rax),%rax=20 0x18021b9e0 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+144>: cm= p 0x20(%rbp),%rax=20 0x18021b9e4 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+148>: je= 0x18021b9f4 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+164>=20 =3D> 0x18021b9e6 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+150= >: mov -0x8(%rbp),%rax=20 0x18021b9ea <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+154>: mo= v 0x10(%rax),%rax=20 (gdb)=20 0x18021b9ee <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+158>: mo= v %rax,-0x8(%rbp)=20 0x18021b9f2 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+162>: jm= p 0x18021b9cb <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+123>=20 0x18021b9f4 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+164>: mo= v -0x8(%rbp),%rax=20 0x18021b9f8 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+168>: mo= v 0x10(%rax),%rax=20 0x18021b9fc <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+172>: cm= p 0x20(%rbp),%rax=20 0x18021ba00 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+176>: jn= e 0x18021ba16 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+198>=20 0x18021ba02 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+178>: mo= v -0x8(%rbp),%rax=20 0x18021ba06 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+182>: mo= v 0x10(%rax),%rax=20 0x18021ba0a <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+186>: mo= v 0x10(%rax),%rdx=20 0x18021ba0e <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+190>: mo= v -0x8(%rbp),%rax=20 (gdb) x/gx $rbp-8 #cur 0xff3fca98: 0x0000000601e147c0=20 (gdb) x/gx 0x0000000601e147c0+0x10 #cur->next 0x601e147d0: 0x0000000601e147c0 #identical to cur, into infinite-loop refer to the source code in thread.h: template inline void List_remove (fast_mutex &mx, list_node *&head, list_node *node) { if (!node) return; mx.lock (); if (head) { if (InterlockedCompareExchangePointer ((PVOID volatile *) &head, node->next, node) !=3D node) { list_node *cur =3D head; while (cur->next && node !=3D cur->next) cur =3D cur->next; if (node =3D=3D cur->next) cur->next =3D cur->next->next; } } mx.unlock (); } Re-paste the sample code test-thread.cpp to demo the infinite loop (I fixed= the space deletion issue in my yahoo email): #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; template class Queue { typedef std::deque Container; public: Queue(int _capacity =3D std::numeric_limits::max()) : capacity(_ca= pacity), closed(false) {} bool enqueue(T* d) { if (closed) return false; std::unique_lock lock(mutex); if (d =3D=3D 0) { closed =3D true; empty_cv.notify_all(); return tr= ue; } while (data.size() >=3D capacity) full_cv.wait(lock); data.push_back(d); empty_cv.notify_one(); return true; } T* dequeue() { std::unique_lock lock(mutex); while (data.empty() && !closed) empty_cv.wait(lock); if (data.size()) { T* d =3D data.front(); data.pop_front(); full_cv.notify_one(); return d; } else return 0; } size_t size() const { return data.size(); } private: std::mutex mutex; std::condition_variable full_cv, empty_cv; uint32_t capacity; bool closed; Container data; }; struct Node { int data; }; struct Job { Node* node; Queue* recycle; }; static Queue jobs; static void* handle_job(void* arg) { long ithr =3D (long)arg; unsigned long seed =3D time(0) + ithr*1000000; int NS =3D 1000; while (Job* j =3D jobs.dequeue()) { struct timespec ts; ts.tv_sec =3D 0; seed =3D seed * 1103515245 + 12345; ts.tv_nsec =3D seed%NS; nanosleep(&ts, 0); j->recycle->enqueue(j->node); delete j; } } struct Task { Queue recycle; int size; // number of sub jobs Task(int N) : size(N) { for (int i =3D 0; idata =3D i; Job* job =3D new Job; job->node =3D t; job->recycle =3D &recycle; jobs.enqueue(job); } } ~Task() { int i =3D 0; while (Node* t =3D recycle.dequeue()) { delete t; if (++i =3D=3D size) break; } } }; static string timestamp() { time_t t; struct tm tmp; char buf[80]; t =3D time(NULL); localtime_r(&t, &tmp); strftime(buf, sizeof(buf), "%d-%m-%Y %I:%M:%S", &tmp); return buf; } static void* create_task(void* arg) { long ithr =3D (long)arg; int TASK_NUM =3D 1000000; int one_percent =3D TASK_NUM/100; int TASK_SUB_JOB_NUM =3D 1; int NS =3D 1000; unsigned long seed =3D time(0) + ithr*10000; int i =3D 0; for (; i < TASK_NUM; ++i) { struct timespec ts; ts.tv_sec =3D 0; seed =3D seed * 1103515245 + 12345; ts.tv_nsec =3D seed%NS; nanosleep(&ts, 0); if (i%one_percent =3D=3D 0) { fprintf(stderr, "%s: create_task[%d]: %d%% done\n", timestamp()= .c_str(), ithr, i/one_percent); } Task task(TASK_SUB_JOB_NUM); } fprintf(stderr, "%s: create_task[%d]: %d%% done\n", timestamp().c_str()= , ithr, i/one_percent); } int main() { int NTHR_HANDLE_JOB =3D 4, NTHR_CREATE_TASK =3D 4; std::vector threads(NTHR_HANDLE_JOB+NTHR_CREATE_TASK); int k =3D 0; for (long i =3D 0; i < NTHR_HANDLE_JOB; ++i) { pthread_create(&threads[k++], NULL, handle_job, (void*)i); } for (long i =3D 0; i < NTHR_CREATE_TASK; ++i) { pthread_create(&threads[k++], NULL, create_task, (void*)i); } // wait for create_task thread for (size_t i =3D NTHR_HANDLE_JOB; i < threads.size(); ++i) { pthread_join(threads[i], NULL); } jobs.enqueue(0); // wait for handle_job thread for (size_t i =3D 0; i < NTHR_HANDLE_JOB; ++i) pthread_join(threads[i], NULL); } -------------------------------------------- On Fri, 12/1/17, Corinna Vinschen wrote: Subject: Re: mixed usage of lock protection and lock-free List template cl= ass in thread.h To: cygwin@cygwin.com Date: Friday, December 1, 2017, 9:15 AM =20 On Dec=C2=A0 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=3Dblo= b;f=3Dwinsup/cygwin/thread.h;hb=3D1f42dc2bcf58d3b8629eb13d53de3f69fc314b47#= l110 >=20 > =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=A01= 16=C2=A0 =C2=A0 =C2=A0node->next =3D head;=C2=A0117=C2=A0 =C2=A0while (InterlockedCompareExchangePointer ((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 inline void=C2=A0122 List_remove (fast_mutex &mx, list_node *&head, list_node *node)=C2=A0123 {=C2=A0124=C2=A0 =C2=A0if (!node)=C2=A0125=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_node *cur =3D head;=C2=A0133=C2=A0=C2=A0134=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0whil= e (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->ne= xt =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=C2=A0 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll > #1=C2=A0 0x000007fefd111430 in KERNELBASE!GetCurrentProcess () from /cygdrive/c/Windows/system32/KERNELBASE.dll > #2=C2=A0 0x0000000076fc06c0 in WaitForMultipleObjects () from /cygdrive/c/Windows/system32/kernel32.dll > #3=C2=A0 0x00000001800458ac in cygwait(void*, _LARGE_INTEGER*, unsigned int) () from /usr/bin/cygwin1.dll > #4=C2=A0 0x000000018013d029 in pthread_cond::~pthread_cond() () from /usr/bin/cygwin1.dll > #5=C2=A0 0x000000018013d0dd in pthread_cond::~pthread_cond() () from /usr/bin/cygwin1.dll > #6=C2=A0 0x0000000180141196 in pthread_cond_destroy () from /usr/bin/cygwin1.dll > #7=C2=A0 0x0000000180116d5b in _sigfe () from /usr/bin/cygwin1.dll > #8=C2=A0 0x0000000100908e38 in std::_Sp_counted_ptr_inplace, std::allocator, void ()>, std::allocator, (__gnu_cxx::_Lock_policy)2>::_M_dispose() () > The problem with the current implementation for concurrent insert and delete 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 Harris's solution to use two CAS? =20 First of all, please, please, please fix your MUA!=C2=A0 Just like your mails to cygwin-patches a couple of weeks ago, your mails are pretty much unreadable due to broken line wrapping. =20 Back to business: This code is working since 2003.=C2=A0 So, is that just a theoretical problem, or a practical one?=C2=A0 If the latter, what is broken exactly? =20 However, since you're asking, a lockless implementation where appropriate is always welcome. =20 =20 Thanks, Corinna =20 --=20 Corinna Vinschen=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Ple= ase, send mails regarding Cygwin to Cygwin Maintainer=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 cygwin AT cygwin DOT com Red Hat -----Inline Attachment Follows----- =20 =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