From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 113874 invoked by alias); 14 Feb 2018 07:04:14 -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 113861 invoked by uid 89); 14 Feb 2018 07:04:13 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=2.4 required=5.0 tests=AWL,BAYES_00,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,FREEMAIL_REPLYTO_END_DIGIT,HTML_MESSAGE,RCVD_IN_DNSWL_NONE,SPF_PASS,T_RP_MATCHES_RCVD autolearn=no version=3.3.2 spammy=H*x:KHTML, H*x:Chrome, H*x:AppleWebKit, H*x:Safari X-HELO: sonic301-20.consmr.mail.gq1.yahoo.com Received: from sonic301-20.consmr.mail.gq1.yahoo.com (HELO sonic301-20.consmr.mail.gq1.yahoo.com) (98.137.64.146) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 14 Feb 2018 07:04:10 +0000 Received: from sonic.gate.mail.ne1.yahoo.com by sonic301.consmr.mail.gq1.yahoo.com with HTTP; Wed, 14 Feb 2018 07:04:08 +0000 Date: Wed, 14 Feb 2018 07:04:00 -0000 From: "Xiaofeng Liu via cygwin" Reply-To: Xiaofeng Liu Reply-To: Xiaofeng Liu To: "cygwin@cygwin.com" Message-ID: <1460534026.545542.1518591843449@mail.yahoo.com> In-Reply-To: <1264797847.540865.1518590850864@mail.yahoo.com> References: <1543396632.5417641.1512146709346.ref@mail.yahoo.com> <1543396632.5417641.1512146709346@mail.yahoo.com> <20171201171536.GA4325@calimero.vinschen.de> <1264797847.540865.1518590850864@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 X-SW-Source: 2018-02/txt/msg00155.txt.bz2 Sorry I have to reformat again. Here is the sample code that will hang in cygwin: test-thread.cpp to compile:=C2=A0g++ -std=3Dc++0x test-thread.cpp -lpthread #include #include #include #include #inc= lude #include #include #include #include <= mutex> #include #include #include #include #include using namespace std; templateclass Queue {=C2=A0 =C2=A0 typedef std::deque Containe= r;public:=C2=A0 =C2=A0 Queue(int _capacity =3D std::numeric_limits::ma= x()) : capacity(_capacity), closed(false) {}=C2=A0 =C2=A0 bool enqueue(T* d= )=C2=A0 =C2=A0 {=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (closed) return false;=C2=A0= =C2=A0 =C2=A0 =C2=A0 std::unique_lock lock(mutex);=C2=A0 =C2= =A0 =C2=A0 =C2=A0 if (d =3D=3D 0) { closed =3D true; empty_cv.notify_all();= return true; }=C2=A0 =C2=A0 =C2=A0 =C2=A0 while (data.size() >=3D capacity= )=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 full_cv.wait(lock);=C2=A0 =C2=A0= =C2=A0 =C2=A0 data.push_back(d);=C2=A0 =C2=A0 =C2=A0 =C2=A0 empty_cv.notif= y_one();=C2=A0 =C2=A0 =C2=A0 =C2=A0 return true;=C2=A0 =C2=A0 }=C2=A0 =C2= =A0 T* dequeue()=C2=A0 =C2=A0 {=C2=A0 =C2=A0 =C2=A0 =C2=A0 std::unique_lock= lock(mutex);=C2=A0 =C2=A0 =C2=A0 =C2=A0 while (data.empty() &&= !closed)=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 empty_cv.wait(lock);=C2= =A0 =C2=A0 =C2=A0 =C2=A0 if (data.size()) {=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 T* d =3D data.front();=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = data.pop_front();=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 full_cv.notify_o= ne();=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 return d;=C2=A0 =C2=A0 =C2= =A0 =C2=A0 } else return 0;=C2=A0 =C2=A0 }=C2=A0 =C2=A0 size_t size() const= { return data.size(); } private:=C2=A0 =C2=A0 std::mutex mutex;=C2=A0 =C2=A0 std::condition_variabl= e full_cv, empty_cv;=C2=A0 =C2=A0 uint32_t capacity;=C2=A0 =C2=A0 bool clos= ed;=C2=A0 =C2=A0 Container data;}; struct Node {=C2=A0 =C2=A0 int data;}; struct Job {=C2=A0 =C2=A0 Node* node;=C2=A0 =C2=A0 Queue* recycle;}; static Queue jobs; static void* handle_job(void* arg){=C2=A0 =C2=A0 long ithr =3D (long)arg;= =C2=A0 =C2=A0 unsigned long seed =3D time(0) + ithr*1000000;=C2=A0 =C2=A0 i= nt NS =3D 1000;=C2=A0 =C2=A0 while (Job* j =3D jobs.dequeue()) {=C2=A0 =C2= =A0 =C2=A0 =C2=A0 struct timespec ts;=C2=A0 =C2=A0 =C2=A0 =C2=A0 ts.tv_sec = =3D 0;=C2=A0 =C2=A0 =C2=A0 =C2=A0 seed =3D seed * 1103515245 + 12345;=C2=A0= =C2=A0 =C2=A0 =C2=A0 ts.tv_nsec =3D seed%NS;=C2=A0 =C2=A0 =C2=A0 =C2=A0 na= nosleep(&ts, 0);=C2=A0 =C2=A0 =C2=A0 =C2=A0 j->recycle->enqueue(j->node);= =C2=A0 =C2=A0 =C2=A0 =C2=A0 delete j;=C2=A0 =C2=A0 }} struct Task {=C2=A0 =C2=A0 Queue recycle;=C2=A0 =C2=A0 int size; // n= umber of sub jobs=C2=A0 =C2=A0 Task(int N) : size(N)=C2=A0 =C2=A0 {=C2=A0 = =C2=A0 =C2=A0 =C2=A0 for (int i =3D 0; idata =3D i;=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Job* job = =3D new Job;=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 job->node =3D t;=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 job->recycle =3D &recycle;=C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 jobs.enqueue(job);=C2=A0 =C2=A0 =C2=A0 =C2= =A0 }=C2=A0 =C2=A0 }=C2=A0 =C2=A0 ~Task()=C2=A0 =C2=A0 {=C2=A0 =C2=A0 =C2= =A0 =C2=A0 int i =3D 0;=C2=A0 =C2=A0 =C2=A0 =C2=A0 while (Node* t =3D recyc= le.dequeue()) {=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 delete t;=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (++i =3D=3D size) break;=C2=A0 =C2=A0= =C2=A0 =C2=A0 }=C2=A0 =C2=A0 }}; static string timestamp(){=C2=A0 =C2=A0 time_t t;=C2=A0 =C2=A0 struct tm tm= p;=C2=A0 =C2=A0 char buf[80];=C2=A0 =C2=A0 t =3D time(NULL);=C2=A0 =C2=A0 l= ocaltime_r(&t, &tmp);=C2=A0 =C2=A0 strftime(buf, sizeof(buf), "%d-%m-%Y %I:= %M:%S", &tmp);=C2=A0 =C2=A0 return buf;} static void* create_task(void* arg){=C2=A0 =C2=A0 long ithr =3D (long)arg;= =C2=A0 =C2=A0 int TASK_NUM =3D 1000000;=C2=A0 =C2=A0 int one_percent =3D TA= SK_NUM/100;=C2=A0 =C2=A0 int TASK_SUB_JOB_NUM =3D 1;=C2=A0 =C2=A0 int NS = =3D 1000;=C2=A0 =C2=A0 unsigned long seed =3D time(0) + ithr*10000;=C2=A0 = =C2=A0 int i =3D 0;=C2=A0 =C2=A0 for (; i < TASK_NUM; ++i) {=C2=A0 =C2=A0 = =C2=A0 =C2=A0 struct timespec ts;=C2=A0 =C2=A0 =C2=A0 =C2=A0 ts.tv_sec =3D = 0;=C2=A0 =C2=A0 =C2=A0 =C2=A0 seed =3D seed * 1103515245 + 12345;=C2=A0 =C2= =A0 =C2=A0 =C2=A0 ts.tv_nsec =3D seed%NS;=C2=A0 =C2=A0 =C2=A0 =C2=A0 nanosl= eep(&ts, 0);=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (i%one_percent =3D=3D 0) {=C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 fprintf(stderr, "%s: create_task[%d]: %= d%% done\n", timestamp().c_str(), ithr, i/one_percent);=C2=A0 =C2=A0 =C2=A0= =C2=A0 }=C2=A0 =C2=A0 =C2=A0 =C2=A0 Task task(TASK_SUB_JOB_NUM);=C2=A0 =C2= =A0 }=C2=A0 =C2=A0 fprintf(stderr, "%s: create_task[%d]: %d%% done\n", time= stamp().c_str(), ithr, i/one_percent);} int main(){=C2=A0 =C2=A0 int NTHR_HANDLE_JOB =3D 4, NTHR_CREATE_TASK =3D 4;= =C2=A0 =C2=A0 std::vector threads(NTHR_HANDLE_JOB+NTHR_CREATE_TA= SK);=C2=A0 =C2=A0 int k =3D 0;=C2=A0 =C2=A0 for (long i =3D 0; i < NTHR_HAN= DLE_JOB; ++i) {=C2=A0 =C2=A0 =C2=A0 =C2=A0 pthread_create(&threads[k++], NU= LL, handle_job, (void*)i);=C2=A0 =C2=A0 }=C2=A0 =C2=A0 for (long i =3D 0; i= < NTHR_CREATE_TASK; ++i) {=C2=A0 =C2=A0 =C2=A0 =C2=A0 pthread_create(&thre= ads[k++], NULL, create_task, (void*)i);=C2=A0 =C2=A0 }=C2=A0 =C2=A0 // wait= for create_task thread=C2=A0 =C2=A0 for (size_t i =3D NTHR_HANDLE_JOB; i <= threads.size(); ++i) {=C2=A0 =C2=A0 =C2=A0 =C2=A0 pthread_join(threads[i],= NULL);=C2=A0 =C2=A0 }=C2=A0 =C2=A0 jobs.enqueue(0);=C2=A0 =C2=A0 // wait f= or handle_job thread=C2=A0 =C2=A0 for (size_t i =3D 0; i < NTHR_HANDLE_JOB;= ++i)=C2=A0 =C2=A0 =C2=A0 =C2=A0 pthread_join(threads[i], NULL);} In this code, mutex and cond need be created and destroyed very frequently,= which could corrupt the static list object owned by some classes in thread= .h. In my test, I have a computer of 8 threads to run cygwin, and the hang = could happen when cond/mutex objects are created and destroyed for the orde= r of 1 millions times within a few minutes. I can also observe that the peak memory kept increasing to a few hundred MB= , and I suspect there is a MEMORY LEAK in cygwin kernel.=C2=A0 I hope the format will be good. If not, I will try again. Thanks.=C2=A0 Xiaofeng From: Corinna Vinschen To: cygwin@cygwin.com=20 Sent: Friday, December 1, 2017 9:15 AM Subject: Re: mixed usage of lock protection and lock-free List template cl= ass in thread.h =20=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=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=C2=A0 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects () from /cy= gdrive/c/Windows/SYSTEM32/ntdll.dll > #1=C2=A0 0x000007fefd111430 in KERNELBASE!GetCurrentProcess () from /cygd= rive/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 i= nt) () 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/cygw= in1.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 ()>, s= td::allocator, (__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!=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. 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? However, since you're asking, a lockless implementation where appropriate is always welcome. Thanks, Corinna --=20 Corinna Vinschen=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 Please, send mails regarding Cygwin to Cygwin Maintainer=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 cy= gwin AT cygwin DOT com Red Hat =20=20=20 =20=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