* mixed usage of lock protection and lock-free List template class in thread.h [not found] <1543396632.5417641.1512146709346.ref@mail.yahoo.com> @ 2017-12-01 16:45 ` Xiaofeng Liu via cygwin 2017-12-01 17:15 ` Corinna Vinschen 0 siblings, 1 reply; 7+ messages in thread From: Xiaofeng Liu via cygwin @ 2017-12-01 16:45 UTC (permalink / raw) To: The Cygwin Mailing List Lock protection and lock-free should never be mixed ! https://cygwin.com/git/gitweb.cgi?p=newlib-cygwin.git;a=blob;f=winsup/cygwin/thread.h;hb=1f42dc2bcf58d3b8629eb13d53de3f69fc314b47#l110 110 template <class list_node> inline void 111 List_insert (list_node *&head, list_node *node) 112 { 113 if (!node) 114 return; 115 do 116 node->next = head; 117 while (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 118 node, node->next) != node->next); 119 } 120 121 template <class list_node> inline void 122 List_remove (fast_mutex &mx, list_node *&head, list_node *node) 123 { 124 if (!node) 125 return; 126 mx.lock (); 127 if (head) 128 { 129 if (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 130 node->next, node) != node) 131 { 132 list_node *cur = head; 133 134 while (cur->next && node != cur->next) 135 cur = cur->next; 136 if (node == cur->next) 137 cur->next = cur->next->next; 138 } 139 } 140 mx.unlock (); 141 } 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/Windows/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.dll #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::allocator<int>, (__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 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? Thanks. Xiaofeng Liu | | | | | | | | | | | Non-blocking linked list Several strategies for implementing non-blocking lists have been suggested. | | | | -- 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: mixed usage of lock protection and lock-free List template class in thread.h 2017-12-01 16:45 ` mixed usage of lock protection and lock-free List template class in thread.h Xiaofeng Liu via cygwin @ 2017-12-01 17:15 ` Corinna Vinschen 2018-02-14 6:47 ` Xiaofeng Liu via cygwin 0 siblings, 1 reply; 7+ messages in thread From: Corinna Vinschen @ 2017-12-01 17:15 UTC (permalink / raw) To: cygwin [-- Attachment #1: Type: text/plain, Size: 3312 bytes --] On Dec 1 16:45, Xiaofeng Liu via cygwin wrote: > Lock protection and lock-free should never be mixed ! > https://cygwin.com/git/gitweb.cgi?p=newlib-cygwin.git;a=blob;f=winsup/cygwin/thread.h;hb=1f42dc2bcf58d3b8629eb13d53de3f69fc314b47#l110 > > 110 template <class list_node> inline void 111 List_insert (list_node *&head, list_node *node) 112 { 113 if (!node) 114 return; 115 do 116 node->next = head; 117 while (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 118 node, node->next) != node->next); 119 } 120 121 template <class list_node> inline void 122 List_remove (fast_mutex &mx, list_node *&head, list_node *node) 123 { 124 if (!node) 125 return; 126 mx.lock (); 127 if (head) 128 { 129 if (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 130 node->next, node) != node) 131 { 132 list_node *cur = head; 133 134 while (cur->next && node != cur->next) 135 cur = cur->next; 136 if (node == cur->next) 137 cur->next = cur->next->next; 138 } 139 } 140 mx.unlock (); 141 } > 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/Windows/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.dll > #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::allocator<int>, (__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 > > 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? 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 -- Corinna Vinschen Please, send mails regarding Cygwin to Cygwin Maintainer cygwin AT cygwin DOT com Red Hat [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 819 bytes --] ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: mixed usage of lock protection and lock-free List template class in thread.h 2017-12-01 17:15 ` Corinna Vinschen @ 2018-02-14 6:47 ` Xiaofeng Liu via cygwin 2018-02-14 7:04 ` Xiaofeng Liu via cygwin 0 siblings, 1 reply; 7+ messages in thread From: Xiaofeng Liu via cygwin @ 2018-02-14 6:47 UTC (permalink / raw) To: cygwin Here is the sample code that will hang in cygwin: test-thread.cpp to compile: g++ -std=c++0x test-thread.cpp -lpthread #include <stdio.h>#include <stdlib.h>#include <thread>#include <vector>#include <string>#include <ctime>#include <climits>#include <cassert>#include <mutex>#include <condition_variable> #include <deque>#include <mutex>#include <pthread.h>#include <cstdint>using namespace std; template<class T>class Queue { typedef std::deque<T*> Container;public: Queue(int _capacity = std::numeric_limits<int>::max()) : capacity(_capacity), closed(false) {} bool enqueue(T* d) { if (closed) return false; std::unique_lock<std::mutex> lock(mutex); if (d == 0) { closed = true; empty_cv.notify_all(); return true; } while (data.size() >= capacity) full_cv.wait(lock); data.push_back(d); empty_cv.notify_one(); return true; } T* dequeue() { std::unique_lock<std::mutex> lock(mutex); while (data.empty() && !closed) empty_cv.wait(lock); if (data.size()) { T* d = 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<Node>* recycle;}; static Queue<Job> jobs; static void* handle_job(void* arg){ long ithr = (long)arg; unsigned long seed = time(0) + ithr*1000000; int NS = 1000; while (Job* j = jobs.dequeue()) { struct timespec ts; ts.tv_sec = 0; seed = seed * 1103515245 + 12345; ts.tv_nsec = seed%NS; nanosleep(&ts, 0); j->recycle->enqueue(j->node); delete j; }} struct Task { Queue<Node> recycle; int size; // number of sub jobs Task(int N) : size(N) { for (int i = 0; i<N; ++i) { Node* t = new Node(); t->data = i; Job* job = new Job; job->node = t; job->recycle = &recycle; jobs.enqueue(job); } } ~Task() { int i = 0; while (Node* t = recycle.dequeue()) { delete t; if (++i == size) break; } }}; static string timestamp(){ time_t t; struct tm tmp; char buf[80]; t = 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 = (long)arg; int TASK_NUM = 1000000; int one_percent = TASK_NUM/100; int TASK_SUB_JOB_NUM = 1; int NS = 1000; unsigned long seed = time(0) + ithr*10000; int i = 0; for (; i < TASK_NUM; ++i) { struct timespec ts; ts.tv_sec = 0; seed = seed * 1103515245 + 12345; ts.tv_nsec = seed%NS; nanosleep(&ts, 0); if (i%one_percent == 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 = 4, NTHR_CREATE_TASK = 4; std::vector<pthread_t> threads(NTHR_HANDLE_JOB+NTHR_CREATE_TASK); int k = 0; for (long i = 0; i < NTHR_HANDLE_JOB; ++i) { pthread_create(&threads[k++], NULL, handle_job, (void*)i); } for (long i = 0; i < NTHR_CREATE_TASK; ++i) { pthread_create(&threads[k++], NULL, create_task, (void*)i); } // wait for create_task thread for (size_t i = NTHR_HANDLE_JOB; i < threads.size(); ++i) { pthread_join(threads[i], NULL); } jobs.enqueue(0); // wait for handle_job thread for (size_t i = 0; i < NTHR_HANDLE_JOB; ++i) 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 order 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. I hope the format will be good. If not, I will try again. Thanks. From: Corinna Vinschen <corinna-cygwin@cygwin.com> To: cygwin@cygwin.com Sent: Friday, December 1, 2017 9:15 AM Subject: Re: mixed usage of lock protection and lock-free List template class in thread.h On Dec 1 16:45, Xiaofeng Liu via cygwin wrote: > Lock protection and lock-free should never be mixed ! > https://cygwin.com/git/gitweb.cgi?p=newlib-cygwin.git;a=blob;f=winsup/cygwin/thread.h;hb=1f42dc2bcf58d3b8629eb13d53de3f69fc314b47#l110 > > 110 template <class list_node> inline void 111 List_insert (list_node *&head, list_node *node) 112 { 113 if (!node) 114 return; 115 do 116 node->next = head; 117 while (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 118 node, node->next) != node->next); 119 } 120 121 template <class list_node> inline void 122 List_remove (fast_mutex &mx, list_node *&head, list_node *node) 123 { 124 if (!node) 125 return; 126 mx.lock (); 127 if (head) 128 { 129 if (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 130 node->next, node) != node) 131 { 132 list_node *cur = head; 133 134 while (cur->next && node != cur->next) 135 cur = cur->next; 136 if (node == cur->next) 137 cur->next = cur->next->next; 138 } 139 } 140 mx.unlock (); 141 } > 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/Windows/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.dll > #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::allocator<int>, (__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 > > 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? 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 -- Corinna Vinschen Please, send mails regarding Cygwin to Cygwin Maintainer cygwin AT cygwin DOT com Red Hat -- 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: mixed usage of lock protection and lock-free List template class in thread.h 2018-02-14 6:47 ` Xiaofeng Liu via cygwin @ 2018-02-14 7:04 ` Xiaofeng Liu via cygwin 2018-02-14 7:37 ` Xiaofeng Liu via cygwin 0 siblings, 1 reply; 7+ messages in thread From: Xiaofeng Liu via cygwin @ 2018-02-14 7:04 UTC (permalink / raw) To: cygwin Sorry I have to reformat again. Here is the sample code that will hang in cygwin: test-thread.cpp to compile: g++ -std=c++0x test-thread.cpp -lpthread #include <stdio.h>#include <stdlib.h>#include <thread>#include <vector>#include <string>#include <ctime>#include <climits>#include <cassert>#include <mutex> #include <condition_variable>#include <deque>#include <mutex>#include <pthread.h>#include <cstdint>using namespace std; template<class T>class Queue { typedef std::deque<T*> Container;public: Queue(int _capacity = std::numeric_limits<int>::max()) : capacity(_capacity), closed(false) {} bool enqueue(T* d) { if (closed) return false; std::unique_lock<std::mutex> lock(mutex); if (d == 0) { closed = true; empty_cv.notify_all(); return true; } while (data.size() >= capacity) full_cv.wait(lock); data.push_back(d); empty_cv.notify_one(); return true; } T* dequeue() { std::unique_lock<std::mutex> lock(mutex); while (data.empty() && !closed) empty_cv.wait(lock); if (data.size()) { T* d = 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<Node>* recycle;}; static Queue<Job> jobs; static void* handle_job(void* arg){ long ithr = (long)arg; unsigned long seed = time(0) + ithr*1000000; int NS = 1000; while (Job* j = jobs.dequeue()) { struct timespec ts; ts.tv_sec = 0; seed = seed * 1103515245 + 12345; ts.tv_nsec = seed%NS; nanosleep(&ts, 0); j->recycle->enqueue(j->node); delete j; }} struct Task { Queue<Node> recycle; int size; // number of sub jobs Task(int N) : size(N) { for (int i = 0; i<N; ++i) { Node* t = new Node(); t->data = i; Job* job = new Job; job->node = t; job->recycle = &recycle; jobs.enqueue(job); } } ~Task() { int i = 0; while (Node* t = recycle.dequeue()) { delete t; if (++i == size) break; } }}; static string timestamp(){ time_t t; struct tm tmp; char buf[80]; t = 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 = (long)arg; int TASK_NUM = 1000000; int one_percent = TASK_NUM/100; int TASK_SUB_JOB_NUM = 1; int NS = 1000; unsigned long seed = time(0) + ithr*10000; int i = 0; for (; i < TASK_NUM; ++i) { struct timespec ts; ts.tv_sec = 0; seed = seed * 1103515245 + 12345; ts.tv_nsec = seed%NS; nanosleep(&ts, 0); if (i%one_percent == 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 = 4, NTHR_CREATE_TASK = 4; std::vector<pthread_t> threads(NTHR_HANDLE_JOB+NTHR_CREATE_TASK); int k = 0; for (long i = 0; i < NTHR_HANDLE_JOB; ++i) { pthread_create(&threads[k++], NULL, handle_job, (void*)i); } for (long i = 0; i < NTHR_CREATE_TASK; ++i) { pthread_create(&threads[k++], NULL, create_task, (void*)i); } // wait for create_task thread for (size_t i = NTHR_HANDLE_JOB; i < threads.size(); ++i) { pthread_join(threads[i], NULL); } jobs.enqueue(0); // wait for handle_job thread for (size_t i = 0; i < NTHR_HANDLE_JOB; ++i) 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 order 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. I hope the format will be good. If not, I will try again. Thanks. Xiaofeng From: Corinna Vinschen <corinna-cygwin@cygwin.com> To: cygwin@cygwin.com Sent: Friday, December 1, 2017 9:15 AM Subject: Re: mixed usage of lock protection and lock-free List template class in thread.h On Dec 1 16:45, Xiaofeng Liu via cygwin wrote: > Lock protection and lock-free should never be mixed ! > https://cygwin.com/git/gitweb.cgi?p=newlib-cygwin.git;a=blob;f=winsup/cygwin/thread.h;hb=1f42dc2bcf58d3b8629eb13d53de3f69fc314b47#l110 > > 110 template <class list_node> inline void 111 List_insert (list_node *&head, list_node *node) 112 { 113 if (!node) 114 return; 115 do 116 node->next = head; 117 while (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 118 node, node->next) != node->next); 119 } 120 121 template <class list_node> inline void 122 List_remove (fast_mutex &mx, list_node *&head, list_node *node) 123 { 124 if (!node) 125 return; 126 mx.lock (); 127 if (head) 128 { 129 if (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 130 node->next, node) != node) 131 { 132 list_node *cur = head; 133 134 while (cur->next && node != cur->next) 135 cur = cur->next; 136 if (node == cur->next) 137 cur->next = cur->next->next; 138 } 139 } 140 mx.unlock (); 141 } > 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/Windows/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.dll > #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::allocator<int>, (__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 > > 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? 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 -- Corinna Vinschen Please, send mails regarding Cygwin to Cygwin Maintainer cygwin AT cygwin DOT com Red Hat -- 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: mixed usage of lock protection and lock-free List template class in thread.h 2018-02-14 7:04 ` Xiaofeng Liu via cygwin @ 2018-02-14 7:37 ` Xiaofeng Liu via cygwin 2018-02-14 14:30 ` Corinna Vinschen 0 siblings, 1 reply; 7+ messages in thread From: Xiaofeng Liu via cygwin @ 2018-02-14 7:37 UTC (permalink / raw) To: cygwin Sorry, I need send again for another try for the formatting. (Yahoo deleted my spaces. Please reformat the code in your C++ editor if you want to use the code. Sorry!) Here is the sample code that will hang in cygwin: test-thread.cpp to compile: g++ -std=c++0x test-thread.cpp -lpthread 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 order of 1 millions times within a few minutes. Is this practical? Yes. My code for my product used a lot of std::future which use one mutex and one mutex for each object. The future objects are created and destroyed on the flight, so are for mutex and cond variables. 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. I hope the format will be good. If not, I will try again. Thanks. Xiaofeng -----------------------------test-thread.cpp------------------- #include <stdio.h> #include <stdlib.h> #include <thread> #include <vector> #include <string> #include <ctime> #include <climits> #include <cassert> #include <mutex> #include <condition_variable> #include <deque> #include <mutex> #include <pthread.h> #include <cstdint> using namespace std; template<class T> class Queue { typedef std::deque<T*> Container; public: Queue(int _capacity = std::numeric_limits<int>::max()) : capacity(_capacity), closed(false) {} bool enqueue(T* d) { if (closed) return false; std::unique_lock<std::mutex> lock(mutex); if (d == 0) { closed = true; empty_cv.notify_all(); return true; } while (data.size() >= capacity) full_cv.wait(lock); data.push_back(d); empty_cv.notify_one(); return true; } T* dequeue() { std::unique_lock<std::mutex> lock(mutex); while (data.empty() && !closed) empty_cv.wait(lock); if (data.size()) { T* d = 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<Node>* recycle; }; static Queue<Job> jobs; static void* handle_job(void* arg) { long ithr = (long)arg; unsigned long seed = time(0) + ithr*1000000; int NS = 1000; while (Job* j = jobs.dequeue()) { struct timespec ts; ts.tv_sec = 0; seed = seed * 1103515245 + 12345; ts.tv_nsec = seed%NS; nanosleep(&ts, 0); j->recycle->enqueue(j->node); delete j; } } struct Task { Queue<Node> recycle; int size; // number of sub jobs Task(int N) : size(N) { for (int i = 0; i<N; ++i) { Node* t = new Node(); t->data = i; Job* job = new Job; job->node = t; job->recycle = &recycle; jobs.enqueue(job); } } ~Task() { int i = 0; while (Node* t = recycle.dequeue()) { delete t; if (++i == size) break; } } }; static string timestamp() { time_t t; struct tm tmp; char buf[80]; t = 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 = (long)arg; int TASK_NUM = 1000000; int one_percent = TASK_NUM/100; int TASK_SUB_JOB_NUM = 1; int NS = 1000; unsigned long seed = time(0) + ithr*10000; int i = 0; for (; i < TASK_NUM; ++i) { struct timespec ts; ts.tv_sec = 0; seed = seed * 1103515245 + 12345; ts.tv_nsec = seed%NS; nanosleep(&ts, 0); if (i%one_percent == 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 = 4, NTHR_CREATE_TASK = 4; std::vector<pthread_t> threads(NTHR_HANDLE_JOB+NTHR_CREATE_TASK); int k = 0; for (long i = 0; i < NTHR_HANDLE_JOB; ++i) { pthread_create(&threads[k++], NULL, handle_job, (void*)i); } for (long i = 0; i < NTHR_CREATE_TASK; ++i) { pthread_create(&threads[k++], NULL, create_task, (void*)i); } // wait for create_task thread for (size_t i = NTHR_HANDLE_JOB; i < threads.size(); ++i) { pthread_join(threads[i], NULL); } jobs.enqueue(0); // wait for handle_job thread for (size_t i = 0; i < NTHR_HANDLE_JOB; ++i) pthread_join(threads[i], NULL); } ----------------------------end of test-thread.cpp-------------------------- To: cygwin@cygwin.com Sent: Friday, December 1, 2017 9:15 AM Subject: Re: mixed usage of lock protection and lock-free List template class in thread.h On Dec 1 16:45, Xiaofeng Liu via cygwin wrote: > Lock protection and lock-free should never be mixed ! > https://cygwin.com/git/gitweb.cgi?p=newlib-cygwin.git;a=blob;f=winsup/cygwin/thread.h;hb=1f42dc2bcf58d3b8629eb13d53de3f69fc314b47#l110 > > 110 template <class list_node> inline void 111 List_insert (list_node *&head, list_node *node) 112 { 113 if (!node) 114 return; 115 do 116 node->next = head; 117 while (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 118 node, node->next) != node->next); 119 } 120 121 template <class list_node> inline void 122 List_remove (fast_mutex &mx, list_node *&head, list_node *node) 123 { 124 if (!node) 125 return; 126 mx.lock (); 127 if (head) 128 { 129 if (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 130 node->next, node) != node) 131 { 132 list_node *cur = head; 133 134 while (cur->next && node != cur->next) 135 cur = cur->next; 136 if (node == cur->next) 137 cur->next = cur->next->next; 138 } 139 } 140 mx.unlock (); 141 } > 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/Windows/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.dll > #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::allocator<int>, (__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 > > 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? 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 -- Corinna Vinschen Please, send mails regarding Cygwin to Cygwin Maintainer cygwin AT cygwin DOT com Red Hat -- 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: mixed usage of lock protection and lock-free List template class in thread.h 2018-02-14 7:37 ` Xiaofeng Liu via cygwin @ 2018-02-14 14:30 ` Corinna Vinschen 0 siblings, 0 replies; 7+ messages in thread From: Corinna Vinschen @ 2018-02-14 14:30 UTC (permalink / raw) To: cygwin [-- Attachment #1: Type: text/plain, Size: 1758 bytes --] On Feb 14 07:37, Xiaofeng Liu via cygwin wrote: > Sorry, I need send again for another try for the formatting. > > > (Yahoo deleted my spaces. Please reformat the code in your C++ editor > if you want to use the code. Sorry!) You may want to use a good old MUA like thunderbird or mutt :} > Here is the sample code that will hang in cygwin: test-thread.cpp > to compile: > g++ -std=c++0x test-thread.cpp -lpthread > 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 order of 1 millions times within a few minutes. > Is this practical? Yes. My code for my product used a lot of > std::future which use one mutex and one mutex for each object. The > future objects are created and destroyed on the flight, so are for > mutex and cond variables. 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. > I hope the format will be good. If not, I will try again. The leading spaces are still gone but at least the linefeeds have been retained, so all is good. Note that this is not sufficient for patch submissions. Make sure to send them as attachment as long as you're using a broken MUA. Thanks for the example. If you can come up with a patch for a lockless implementation this would be highly appreciated. Thanks, Corinna -- Corinna Vinschen Please, send mails regarding Cygwin to Cygwin Maintainer cygwin AT cygwin DOT com Red Hat [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 833 bytes --] ^ permalink raw reply [flat|nested] 7+ messages in thread
[parent not found: <451353526.1938418.1518798301806.ref@mail.yahoo.com>]
* Re: mixed usage of lock protection and lock-free List template class in thread.h [not found] <451353526.1938418.1518798301806.ref@mail.yahoo.com> @ 2018-02-16 16:25 ` Xiaofeng Liu via cygwin 0 siblings, 0 replies; 7+ messages in thread From: Xiaofeng Liu via cygwin @ 2018-02-16 16:25 UTC (permalink / raw) To: cygwin Here is more detailed information to demo the infinite loop due to corruption of the list, using one "-g" compiled cygwin1.dll in my cygwin: After the job hang, the stacks are: (gdb) info thread Id Target Id Frame * 11 Thread 15220.0x1ef0 0x000000007711afb1 in ntdll!DbgBreakPoint () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll 10 Thread 15220.0x1274 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll 9 Thread 15220.0x28c4 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll 8 Thread 15220.0x3f1c 0x000000018021b9e6 in void List_remove<pthread_mutex>(fast_mutex&, pthread_mutex*&, pthread_mutex*) () from /usr/bin/cygwin1.dll 7 Thread 15220.0x20a8 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll 6 Thread 15220.0x1980 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll 5 Thread 15220.0x389c 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll 4 Thread 15220.0x3c1c 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll 3 Thread 15220.0x3290 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll 2 Thread 15220.0x3db0 0x000000007711bd9a in ntdll!ZwReadFile () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll 1 Thread 15220.0xf6c 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll (gdb) thread 8 [Switching to thread 8 (Thread 15220.0x3f1c)] #0 0x000000018021b9e6 in void List_remove<pthread_mutex>(fast_mutex&, pthread_mutex*&, pthread_mutex*) () from /usr/bin/cygwin1.dll (gdb) x/10i $pc => 0x18021b9e6 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+150>: mov -0x8(%rbp),%rax 0x18021b9ea <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+154>: mov 0x10(%rax),%rax 0x18021b9ee <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+158>: mov %rax,-0x8(%rbp) 0x18021b9f2 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+162>: jmp 0x18021b9cb <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+123> 0x18021b9f4 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+164>: mov -0x8(%rbp),%rax 0x18021b9f8 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+168>: mov 0x10(%rax),%rax 0x18021b9fc <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+172>: cmp 0x20(%rbp),%rax 0x18021ba00 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+176>: jne 0x18021ba16 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+198> 0x18021ba02 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+178>: mov -0x8(%rbp),%rax 0x18021ba06 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+182>: mov 0x10(%rax),%rax (gdb) x/10i $pc-150+123 0x18021b9cb <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+123>: mov -0x8(%rbp),%rax 0x18021b9cf <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+127>: mov 0x10(%rax),%rax 0x18021b9d3 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+131>: test %rax,%rax 0x18021b9d6 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+134>: je 0x18021b9f4 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+164> 0x18021b9d8 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+136>: mov -0x8(%rbp),%rax 0x18021b9dc <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+140>: mov 0x10(%rax),%rax 0x18021b9e0 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+144>: cmp 0x20(%rbp),%rax 0x18021b9e4 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+148>: je 0x18021b9f4 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+164> => 0x18021b9e6 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+150>: mov -0x8(%rbp),%rax 0x18021b9ea <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+154>: mov 0x10(%rax),%rax (gdb) 0x18021b9ee <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+158>: mov %rax,-0x8(%rbp) 0x18021b9f2 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+162>: jmp 0x18021b9cb <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+123> 0x18021b9f4 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+164>: mov -0x8(%rbp),%rax 0x18021b9f8 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+168>: mov 0x10(%rax),%rax 0x18021b9fc <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+172>: cmp 0x20(%rbp),%rax 0x18021ba00 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+176>: jne 0x18021ba16 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+198> 0x18021ba02 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+178>: mov -0x8(%rbp),%rax 0x18021ba06 <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+182>: mov 0x10(%rax),%rax 0x18021ba0a <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+186>: mov 0x10(%rax),%rdx 0x18021ba0e <_Z11List_removeI13pthread_mutexEvR10fast_mutexRPT_S4_+190>: mov -0x8(%rbp),%rax (gdb) x/gx $rbp-8 #cur 0xff3fca98: 0x0000000601e147c0 (gdb) x/gx 0x0000000601e147c0+0x10 #cur->next 0x601e147d0: 0x0000000601e147c0 #identical to cur, into infinite-loop refer to the source code in thread.h: template <class list_node> 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) != node) { list_node *cur = head; while (cur->next && node != cur->next) cur = cur->next; if (node == cur->next) cur->next = 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 <stdio.h> #include <stdlib.h> #include <thread> #include <vector> #include <string> #include <ctime> #include <climits> #include <cassert> #include <mutex> #include <condition_variable> #include <deque> #include <mutex> #include <pthread.h> #include <cstdint> using namespace std; template<class T> class Queue { typedef std::deque<T*> Container; public: Queue(int _capacity = std::numeric_limits<int>::max()) : capacity(_capacity), closed(false) {} bool enqueue(T* d) { if (closed) return false; std::unique_lock<std::mutex> lock(mutex); if (d == 0) { closed = true; empty_cv.notify_all(); return true; } while (data.size() >= capacity) full_cv.wait(lock); data.push_back(d); empty_cv.notify_one(); return true; } T* dequeue() { std::unique_lock<std::mutex> lock(mutex); while (data.empty() && !closed) empty_cv.wait(lock); if (data.size()) { T* d = 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<Node>* recycle; }; static Queue<Job> jobs; static void* handle_job(void* arg) { long ithr = (long)arg; unsigned long seed = time(0) + ithr*1000000; int NS = 1000; while (Job* j = jobs.dequeue()) { struct timespec ts; ts.tv_sec = 0; seed = seed * 1103515245 + 12345; ts.tv_nsec = seed%NS; nanosleep(&ts, 0); j->recycle->enqueue(j->node); delete j; } } struct Task { Queue<Node> recycle; int size; // number of sub jobs Task(int N) : size(N) { for (int i = 0; i<N; ++i) { Node* t = new Node(); t->data = i; Job* job = new Job; job->node = t; job->recycle = &recycle; jobs.enqueue(job); } } ~Task() { int i = 0; while (Node* t = recycle.dequeue()) { delete t; if (++i == size) break; } } }; static string timestamp() { time_t t; struct tm tmp; char buf[80]; t = 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 = (long)arg; int TASK_NUM = 1000000; int one_percent = TASK_NUM/100; int TASK_SUB_JOB_NUM = 1; int NS = 1000; unsigned long seed = time(0) + ithr*10000; int i = 0; for (; i < TASK_NUM; ++i) { struct timespec ts; ts.tv_sec = 0; seed = seed * 1103515245 + 12345; ts.tv_nsec = seed%NS; nanosleep(&ts, 0); if (i%one_percent == 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 = 4, NTHR_CREATE_TASK = 4; std::vector<pthread_t> threads(NTHR_HANDLE_JOB+NTHR_CREATE_TASK); int k = 0; for (long i = 0; i < NTHR_HANDLE_JOB; ++i) { pthread_create(&threads[k++], NULL, handle_job, (void*)i); } for (long i = 0; i < NTHR_CREATE_TASK; ++i) { pthread_create(&threads[k++], NULL, create_task, (void*)i); } // wait for create_task thread for (size_t i = NTHR_HANDLE_JOB; i < threads.size(); ++i) { pthread_join(threads[i], NULL); } jobs.enqueue(0); // wait for handle_job thread for (size_t i = 0; i < NTHR_HANDLE_JOB; ++i) pthread_join(threads[i], NULL); } -------------------------------------------- On Fri, 12/1/17, Corinna Vinschen <corinna-cygwin@cygwin.com> wrote: Subject: Re: mixed usage of lock protection and lock-free List template class in thread.h To: cygwin@cygwin.com Date: Friday, December 1, 2017, 9:15 AM On Dec 1 16:45, Xiaofeng Liu via cygwin wrote: > Lock protection and lock-free should never be mixed ! > https://cygwin.com/git/gitweb.cgi?p=newlib-cygwin.git;a=blob;f=winsup/cygwin/thread.h;hb=1f42dc2bcf58d3b8629eb13d53de3f69fc314b47#l110 > > 110 template <class list_node> inline void 111 List_insert (list_node *&head, list_node *node) 112 { 113 if (!node) 114 return; 115 do 116 node->next = head; 117 while (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 118 node, node->next) != node->next); 119 } 120 121 template <class list_node> inline void 122 List_remove (fast_mutex &mx, list_node *&head, list_node *node) 123 { 124 if (!node) 125 return; 126 mx.lock (); 127 if (head) 128 { 129 if (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 130 node->next, node) != node) 131 { 132 list_node *cur = head; 133 134 while (cur->next && node != cur->next) 135 cur = cur->next; 136 if (node == cur->next) 137 cur->next = cur->next->next; 138 } 139 } 140 mx.unlock (); 141 } > 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/Windows/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.dll > #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::allocator<int>, (__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 > > 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? 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 -- Corinna Vinschen Please, send mails regarding Cygwin to Cygwin Maintainer cygwin AT cygwin DOT com Red Hat -----Inline Attachment Follows----- -- 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2018-02-16 16:25 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <1543396632.5417641.1512146709346.ref@mail.yahoo.com> 2017-12-01 16:45 ` mixed usage of lock protection and lock-free List template class in thread.h Xiaofeng Liu via cygwin 2017-12-01 17:15 ` Corinna Vinschen 2018-02-14 6:47 ` Xiaofeng Liu via cygwin 2018-02-14 7:04 ` Xiaofeng Liu via cygwin 2018-02-14 7:37 ` Xiaofeng Liu via cygwin 2018-02-14 14:30 ` Corinna Vinschen [not found] <451353526.1938418.1518798301806.ref@mail.yahoo.com> 2018-02-16 16:25 ` Xiaofeng Liu via cygwin
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).