* 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
* 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).