Mail Archives: cygwin/2018/02/14/02:37:56
| X-Recipient: | archive-cygwin AT delorie DOT com
|
| DomainKey-Signature: | a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id
|
| :list-unsubscribe:list-subscribe:list-archive:list-post
|
| :list-help:sender:date:from:reply-to:reply-to:to:message-id
|
| :in-reply-to:references:subject:mime-version:content-type
|
| :content-transfer-encoding; q=dns; s=default; b=BMJ/1J4QeZVOkIZ/
|
| LqwylL9r+NSg92uITwZKTG6xwpNYH1UhRULFIjmwdV8UbqGmLYpJpTsB7BegGP5y
|
| LVGcObFq0Qw7fzd6wMaR0Ms37qUVsabhPnBWNDVvEIOkyLD5DBNjrxWUl+BU6Lgk
|
| G6erN4RdBvaE3UkSqFL+xxLwt5U=
|
| DKIM-Signature: | v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id
|
| :list-unsubscribe:list-subscribe:list-archive:list-post
|
| :list-help:sender:date:from:reply-to:reply-to:to:message-id
|
| :in-reply-to:references:subject:mime-version:content-type
|
| :content-transfer-encoding; s=default; bh=HHFyBts52P4zXwfvG1zC6s
|
| qFuqg=; b=NSOB1MszmVwPMJ7fNUa5KdVFITqqNPvjmsfN2uzHh8OdVde0Rbx0As
|
| 9jeh6bBy+PV3oAqHoRzRxEJ6IPpdBoEMkEVs6ZRj1nj4X9rcWESZSg2z1D1OzX9f
|
| MAtqiINurVhIUlfGlIyC/8Tksp594IGPmG335fnlcMztRKrGKH/BU=
|
| Mailing-List: | contact cygwin-help AT cygwin DOT com; run by ezmlm
|
| List-Id: | <cygwin.cygwin.com>
|
| List-Subscribe: | <mailto:cygwin-subscribe AT cygwin DOT com>
|
| List-Archive: | <http://sourceware.org/ml/cygwin/>
|
| List-Post: | <mailto:cygwin AT cygwin DOT com>
|
| List-Help: | <mailto:cygwin-help AT cygwin DOT com>, <http://sourceware.org/ml/#faqs>
|
| Sender: | cygwin-owner AT cygwin DOT com
|
| Mail-Followup-To: | cygwin AT cygwin DOT com
|
| Delivered-To: | mailing list cygwin AT cygwin DOT com
|
| Authentication-Results: | sourceware.org; auth=none
|
| X-Virus-Found: | No
|
| X-Spam-SWARE-Status: | No, score=-2.3 required=5.0 tests=AWL,BAYES_00,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,FREEMAIL_REPLYTO_END_DIGIT,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: | sonic312-23.consmr.mail.gq1.yahoo.com
|
| Date: | Wed, 14 Feb 2018 07:37:38 +0000 (UTC)
|
| From: | "Xiaofeng Liu via cygwin" <cygwin AT cygwin DOT com>
|
| Reply-To: | Xiaofeng Liu <liuxf09 AT yahoo DOT com>
|
| Reply-To: | Xiaofeng Liu <liuxf09 AT yahoo DOT com>
|
| To: | "cygwin AT cygwin DOT com" <cygwin AT cygwin DOT com>
|
| Message-ID: | <1541824013.551552.1518593858391@mail.yahoo.com>
|
| In-Reply-To: | <1460534026.545542.1518591843449@mail.yahoo.com>
|
| References: | <1543396632 DOT 5417641 DOT 1512146709346 DOT ref AT mail DOT yahoo DOT com> <1543396632 DOT 5417641 DOT 1512146709346 AT mail DOT yahoo DOT com> <20171201171536 DOT GA4325 AT calimero DOT vinschen DOT de> <1264797847 DOT 540865 DOT 1518590850864 AT mail DOT yahoo DOT com> <1460534026 DOT 545542 DOT 1518591843449 AT mail DOT yahoo DOT com>
|
| Subject: | Re: mixed usage of lock protection and lock-free List template class in thread.h
|
| MIME-Version: | 1.0
|
| X-MIME-Autoconverted: | from quoted-printable to 8bit by delorie.com id w1E7btbq012325
|
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 AT cygwin DOT 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
- Raw text -